알고리즘/BJ

[BJ] 백준 1065 한수 (JAVA)

문제 https://www.acmicpc.net/problem/1065 풀이 방법 함수 카테고리에 있는 기본 문제다. 나는 한수인지 아닌지 체크해주는 함수를 만들어서 풀이했다. 함수에는 우선 10미만인 수는 모두 한수이기 때문에 true를 반환해주고, 10이상부터는 수를 String으로 변환 후 0번째 값과 1번째 값의 차이를 계산해서 그 차이값을 저장해줬다. 그리고 이제 정수를 한자리수씩 보면서 본인과 그 다음 자리 수의 차이가 이전에 구해놨던 gap과 다르다면 바로 false를 반환해줬다. 그리고 이제 메인함수에서는 true이면 한수이므로 cnt변수에 1를 추가해주었고, 마지막에 cnt를 출력해줬다. 제출 코드 import java.io.*; public class BJ_1065_한수 { public..

[BJ] 백준 13458 시험감독 (JAVA)

문제 https://www.acmicpc.net/problem/13458 풀이 방법 문제는 시험을 보는 반의 개수가 주어지고, 각 반에 학생이 몇명 있는지 주어진다. 총감독과 부감독이 존재하는데 총감독은 1명만 존재해야하고 부감독은 여러명 존재할 수 있다. 총감독이 감시할 수 있는 학생수와 부감독이 감시할 수 있는 학생수가 주어졌을 때 모든 학생을 감시하기 위한 최소 감독 수를 구하는 문제다. 다음과 같은 순서로 풀이했다. 1. N번째 반에서 총 감독관 1명이 존재하므로 sum에 1를 더해준다. 2. 총감독이 감시할 수 있는 학생수를 기존의 학생수에서 빼준다. 3. 남은 학생수가 양수라면 부감독이 감시가능한 학생수를 나눠서 딱 나누어떨어진다면 그 값을, 아니면 1을 더해서 sum에 더해준다. 4. 반의 ..

[BJ] 백준 8958 OX퀴즈 (JAVA)

문제 https://www.acmicpc.net/problem/8958 풀이 방법 단순한 1차원 배열 문제다. O가 나올때는 O이 연속한 개수만큼 점수를 더해주면 되고, 만약 X를 만난다면 다시 0으로 초기화해주면 된다. 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BJ_8958_OX퀴즈 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..

[BJ] 백준 3052 나머지 (JAVA)

문제 https://www.acmicpc.net/problem/3052 풀이 방법 단순한 1차열 배열 문제다. 10개의 수를 입력받고, 각 수를 42로 나눈 나머지의 값을 계산해준다. 그리고 나서 미리 만들어둔 boolean 배열에서 나머지의 값과 동일한 인덱스를 가진 곳을 true로 변경해준다. 30이라는 수가 있다면 42로 나눈 나머지의 값이 30이므로 check[30]의 값이 true로 바뀔 것이다. 그리고나서 마지막에 true의 개수를 세서 출력해준다. 조금더 시간을 줄일려면 check 배열의 값이 true면 countiue를 해줄 순 있겠지만 큰 차이가 없을 것 같아서 그냥 작성하지 않았다. 제출 코드 import java.io.BufferedReader; import java.io.IOExce..

[BJ] 백준 2193 이친 수 (JAVA)

문제 https://www.acmicpc.net/problem/2193 풀이 방법 이 문제도 dp문제다. 0과 1로만 이루어진 수를 이진수라고 하며, 다음과 같은 성질을 만족하는 수를 이친수라고 한다. 1. 0으로 시작하지 않는다. 2. 1이 연속해서 두번 나타나지 않는다. N자리 이친수의 개수를 구하면 된다. 2차원 dp배열을 사용해서 풀이했다. dp[N][0]에는 N자리 수이며 마지막 수가 0인 이친수의 개수, dp[N][1]에는 N자리 수이며 마지막 수가 1인 수의 개수를 저장해줬다. 그리고 이제 반복문을 돌면서 끝자리가 0인 경우에는 1과 0 모두 다 올 수 있으므로 dp[i+1][0], dp[i+1][1] 에 모두 dp[i][0]의 값을 더해줬다. 그리고 끝자리가 1인 경우에는 연속으로 1이 두..

[BJ] 백준 11057 오르막 수 (JAVA)

문제 https://www.acmicpc.net/problem/11057 풀이 방법 한창 DP 문제를 풀 때의 문제들을 올리고 있어서 아마 한동안은 DP문제들만 게시할 것 같다.. 문제를 간단하게 리뷰하면 오르막수는 수가의 자리가 오름차순으로 이루어진 수를 말한다. 이때, 같은 수인 경우에도 오름차순으로 생각한다. 예를들어 1123, 3456, 249 등의 수가 있다. 수의 자리수 N이 주어지면 이 오름차순인 N자리 수의 개수를 구하면 되는 문제다. 이 문제도 DP를 사용해서 풀이했다. 바로 직전의 문제와 동일하게 dp[N][10] 의 2차원 배열을 선언해주고, N은 몇자리 수인지, 그리고 뒤에 0~9는 마지막 자리라고 생각해줬다. 예를 들어 2135 인 숫자는 dp[4][5] 에 포함이 되어있을 것이다..

[BJ] 백준 10844 쉬운 계단 수 (JAVA)

문제 https://www.acmicpc.net/problem/10844 풀이 방법 dp를 사용하는 문제다. dp는 왜 항상 해도해도 새로울까... 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. N이 주어지고 N자리 숫자에서 계단수가 총 몇개 있는지 구하면 되는 문제이다. dp는 2차원 배열로 선언해주고, dp[N][m] : N자리 숫자이고 마지막 자리의 수가 m인 숫자의 개수를 넣어준다고 생각하면 된다. 그래서 반복문 N번 돌면서 j : 0부터 10까지 반복문을 돌린다. j는 마지막 자리 숫자이다. 만약 2343라는 수는 dp[4][3]에 포함이 되는 숫자이다. 어쨌든 반복문을 돌면서 마지막 자리수에 -1, +1을 하는 경우가 0~9사이에 존재한다면 [n+1][j+1] 또는 [n+1][j-1..

[BJ] 백준 2116 주사위쌓기(JAVA)

문제 https://www.acmicpc.net/problem/2116 풀이 방법 구현문제로 브루투포스 알고리즘을 사용하면 된다. 우선 나는 문제에 있는 ABCDEF을 보고 각 마주보는 면의 인덱스를 미리 저장해뒀다. 다음과 같은 순서로 구현했다. 1. 맨 아래에 올 주사위의 윗면을 정해준다. (6면 전부 다 구해보기) 2. 윗면이 정해졌으면 옆면중에서 가장 큰값을 고른다. 3. 윗면의 값과 위에서 골랐던 옆면 중 가장 큰값을 가지고 주사위를 쌓으러 간다. //재귀함수 시작 (아래서 2번째 주사위부터 쌓아올리는 함수) 1. 아래에 있는 주사위의 윗면에 해당하는 값을 현재 주사위에서 찾는다. => 자동으로 윗면의 인덱스가 정해진다. 2. 옆면중에서 가장 큰값을 고른다. 3. 그 다음 주사위를 쌓으러 간다...

[BJ] 백준 11463 1로 만들기(JAVA)

문제 https://www.acmicpc.net/problem/1463 풀이 방법 문제는 간단하다. 1. x가 3으로 나누어떨어지면, 3으로 나누기 2. x가 2로 나우어 떨어지면, 2로 나누기 3. 1를 빼기 위 세개의 연산을 적절히 사용해서 1을 만드는데 연산을 사용하는 횟수의 최소값을 구하는 문제이다. 이 문제는 dp를 사용해서 풀면 된다. dp[N]에는 N이 1이 될때까지의 최소 연산 횟수를 가지고 있다. 우선 N이 2또는 3으로 나누어떨어지는지 확인한다. 만약 나누어 떨어진다면 2로 나눴을 때와 3으로 나눴을때 어떤 수가 더 최소연산 횟수를 가지는지 비교해서 더 작은 값을 dp에 넣는다. 그리고 항상 -1를 했을 경우의 연산의 최소값을 구해서 기존의 dp값과 비교 후, 더 작은 값을 dp에 넣어..