본문 바로가기

다이나믹 프로그래밍27

백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) 문제 : boj11060 N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다. 각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 2022. 1. 10.
백준 2491 자바 - 수열 (BOJ 2491 JAVA) 문제 : boj2491 1. 연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다. 2. 그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하.. 2021. 12. 31.
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) 문제 : boj2225 1. 0부터 N까지에서 '0부터' 부분 때문에 좀 헷갈렸다. '덧셈의 순서가 바뀐 경우는 다른 경우로 센다' 라는 부분 때문에, 예를들어서 N이 1이라 해도 K가 5라면 1+0+0+0+0 / 0+1+0+0+0 / ... / 0+0+0+0+1 이 가능해진다 ㅋㅋㅋ 0의 더하는 순서라니 인지적으로는 좀 이상하긴 하지만, 사실 문제 푸는데는 상관없다! '2'를 보면 알겠지만, 그냥 1부터 N까지라고 해도 점화식이 달라질 뿐이다. 2. K-1개의 수를 합해 만든 어떠한 값이 있다. 이 값에 0부터 N까지의 정수를 더한다면 K-1개의 수로 만든 합에 1개의 정수를 더 더한 것이므로, K개의 수를 사용해 만든 어떠한 합이 될 것이다. 그렇다면 0부터 N까지의 정수를 사용해서, X개의 수를 합.. 2021. 12. 30.
백준 2133 자바 - 타일 채우기 (BOJ 2133 JAVA) 문제 : boj2133 1. 우선, 2x1과 1x2짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. 2. 가장 기본적인 규칙성을 찾아보자. n=2일 때 3가지 모양이 나온다. 3. 그럼 n=4일 때는 n=2일 때 나왔던 모양에서 각각의 경우 3가지 모양이 더 추가되므로 'n=2일때의 모양 x 3'이 됨을 쉽게 알 수 있다. 예를 들어 위 n=2일때 중 첫번째 그림에 대해서만 그려보면 다음과 같다. 일단 여기까지, f(n)을 3 x n 타일링에서 n개의 가로칸으로 가능한 타일링의 경우의 수라 하자. 그럼 f(4) = f(2) * 3 임을 알 수 있다. .. 2021. 12. 30.
백준 2193 자바 - 이친수 (BOJ 2193 JAVA) 문제 : boj2193 1. N=1 일 때를 생각해보자. 0으로 시작하면 안되므로, 0으로 끝나는 수는 0개이고 1로 끝나는 수는 1개이다. (0과 1) 2. N=2 일 때를 생각해보자. 0으로 끝나려면 어떻게 해야 할까? 이 문제의 경우 1이 두번 연속으로 나오지 않기만 하면 된다. 따라서 이전 값이 0으로 끝나거나, 1으로 끝나거나 상관 없이 0을 붙일 수 있다. 반면에 끝이 1로 끝나려면 이전에 0으로 끝난 경우에 대해서만 1을 추가로 붙일 수 있다. 3. 이제 위의 규칙을 계산하기 위해 dp를 사용해보자. dp[n][x(=2)]를 n자리수에서 x로 끝나는 경우의 수라 정의하자. 이 때 n=5인 경우에 대해 그려보면 다음과 같다. 점화식으로 나타내면 dp[n][0] = dp[n-1][0] + dp[.. 2021. 12. 30.
백준 2294 자바 - 동전 2 (BOJ 2294 JAVA) 문제 : boj2294 1. 우선 문제에서 필요없는 정보를 제한해보자. 1.1 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.' -> 이 조건은 해당 가치를 표현하는 경우의 수를 구할때나 의미가 있다. '사용한 동전의 최소 개수'를 구하는 문제이므로 무시해도 된다. 1.2 '가치가 같은 동전이 여러 번 주어질 수도 있다.' -> 가치가 동일한 동전의 경우 연산을 느리게 할 뿐이므로, 동일한 동전이 주어진 경우는 HashSet 등을 사용해 제거하면 될 것임을 생각할 수 있다. 1.3 'k 2021. 12. 30.
백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA) 문제 : boj2806 1. 문자를 하나씩 보면서 전부 A, 혹은 B로 변경해 나간다고 생각해보자. 그렇다면 8가지 경우가 나온다. case1. 현재 문자는 A, 이전까지 전부 A 였음, 전부 A로 유지할 것임 -> 이전 상태에 그냥 A를 붙이면 된다. (돌연변이 +0) case2. 현재 문자는 A, 이전까지 전부 A 였음, 전부 B로 유지할 것임 -> 이전 상태에 그냥 A를 붙인 후, 전체를 B로 변경한다. (돌연변이 +1) case3. 현재 문자는 A, 이전까지 전부 B 였음, 전부 A로 유지할 것임 -> 이전 상태 전체를 A로 변경하고 A를 붙인다. (돌연변이 +1) case4. 현재 문자는 A, 이전까지 전부 B 였음, 전부 B로 유지할 것임 -> 현재 문자를 B로 변경해서 붙인다. (돌연변이 +.. 2021. 12. 19.

티스토리툴바