본문 바로가기

dp58

백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3.
백준 15992 자바 - 1, 2, 3 더하기 7 (BOJ 15992 JAVA) 문제 : boj15992 1. 단순화 해서 생각해보기 우선 '사용한 수의 개수는 m개' 라는 조건이 없다고 생각해보자. 이 경우 1부터 n까지의 1차원 DP로 풀 수 있다. dp[a]를 a를 1,2,3을 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 즉, a를 1부터 n까지 증가시키며 다음의 점화식을 적용한 DP를 진행하면 된다. 2. 사용한 수의 개수가 m개 '1'에서 조건이 하나 더 추가되었다. 그러니 2차원 DP로 확장시키면 된다. dp[a][b]를 a를 1,2,3을 b번 더해서 표현할 수 있는 가지수라고 할 경우, 점화식은 다음과 같을 것이다. 마찬가지로 a는 1부터 n까지 증가시키면 되고, 이 때 b는 1부터 min(a, m) 까지 증가시키면서 구하면 된다(그냥 b도.. 2022. 2. 2.
백준 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.
백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.
백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA) 문제 : boj14002 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다. 2. 추가로 배열을 더 사용해서 .. 2021. 12. 21.

티스토리툴바