소프트웨어개발블로그 소프트웨어개발블로그

풀이 DP 문제를 풀어가면서 가장 중요하다고 느낀 점은 "DP 배열을 어떻게 표현할 것인가" 이다. 지금까지의 DP 문제들은 "DP[x] = 문제에서 요구하는 x 의 결과값" 이었다. 즉 최종적으로 구하고 싶은 값이 x 이어도 DP 배열은 DP[x - y] 에 대하여 해당 x - y 에서의 문제가 요구하는 결과값을 담고 있도록 구성하였다. 그러나 이 문제들은 다르다. DP 배열은 각각 대응되는 결과값으로 초기화 시킨다. 즉, 가장 긴 부분수열 문제의 경우에 10 20 10 30 20 50 의 입력값에 대하여 DP 배열은 idx 1 ~ 7 까지 모두 1 로 초기화 되고 만약 조건을 통과하지 못하면 최종적으로 그대로 1 로 남는다. 이건 아주 큰 차이인데, 좀더 자세히 다음을 보면서 설명해보겠다. 10 20..

풀이 2번 규칙을 보자. 연속으로 놓여있는 3잔을 모두 마실 수는 없다. 이 말은 다음과 같은 것은 가능하다는 것이다. 1. 안마신다. 2. 1 번 연속 마신다. 3. 2 번 연속 마신다. 그리고 DP 배열은 다음과 같이 구성한다. DP[포도잔의 수] = 정답 그렇다면 이 예제의 경우에서 6 10 만이 입력된다면 DP[2] = 16 이다. 만약 6 , 10 , 13 만이 입력된다면 DP[3] = 23 이다. 여기에서 알 수 있는 것은 포도주 3 잔의 최대값을 알려면 3개의 값을 비교해야 한다는 것이다. DP[3] = max ( 6 + 10 , 10 + 13 , 6 + 13 ) = 23 이 식은 또 이렇게 바꿀 수 있다. DP[3] = max ( DP[2] , arr[2] + arr[3] , DP[1] +..

풀이 한 스티커를 사용한 후 좌/우/상/하 에 위치한 스티커를 사용할 수 없다면 이동할 수 있는 위치는 대각선 뿐이다. 이러한 특징을 이용하여 문제를 풀어야한다. 규칙 1. 스티커 위치의 이동은 대각선으로 한다. 그 다음은 한번에 몇칸까지 이동할 수 있는가를 고려해봐야 한다. 이렇게 한번에 1칸, 2칸, 3칸 ... 등을 움직였을때 2 X N 의 최대 가중치가 어떻게 달라지는지 파악하는 것이 중요하다. 위 그림은 70 까지 가는 2가지 방법을 나타내었다. 파란색 : 50 에서 바로 70 으로 이동, 50 + 70 = 120 빨간색 : 30 과 10 을 거쳐서 70 으로 이동, 30 + 10 + 70 = 100 빨간색은 2 번 이동했음에도 불구하고 1 번 이동한 파란색 보다 값이 작다. 항상 이런 결과가 ..

풀이 표를 그려보면 쉽게 풀 수 있다. 그러나 표의 행과 열을 어떤 수로 구성해야 할지는 약간의 고민이 필요하다. (이전 문제와는 다르다.) 문제를 보면 무조건 1 부터 시작해야하며 1 이 나오면 반드시 다음에는 0이 와야하고 0 이 나오면 다음에는 0, 1 이 모두 올 수 있다는 것을 알 수 있다. 규칙은 매우 간단하다. 여기서 바로 점화식으로 옮길 수 있다면 좋을테지만 그런 능력이 아직은 안되기 때문에 표를 그려보았다. 각각의 열은 마지막 자리가 0, 1 인 이친수의 개수를 나타낸다. 예를 들어서 살펴보면 4 자리 수의 경우 1 0 0 0 1 0 0 1 1 0 1 0 이렇게 3 개의 이친수가 존재하므로 끝자리(2^0 의 자리) 가 0 인 것은 2 개, 1 인 것은 1 개가 존재한다. 이렇게 표현해놓고..

풀이 오르막 수 문제는 이전 계단 문제와 마찬가지로 2차원 배열을 활용해서 풀어낼 수 있다. 문제를 읽어보면 각 자리수에 어떤 수 j 가 온다면 그 수의 다음에 올 수 있는 수는 j ~ 9 까지가 된다는 것을 알 수 있다. 점화식은 다음과 같다. DP[N][j] = sum ( DP[N - 1][j ...9] ); 즉, 어떤 값 N 의 특정 자리수 j 의 값은 N - 1 의 자리수의 j 값 부터 9 까지의 모든 해를 더한 것과 같다. ps.. 위 표를 보면 위 값을 전부 더하는 방식(알고리즘에 따른 방식)은 3 중 for 문을 구성해야한다. 그러나 자리값의 해가 DP[N][J] = DP[N][j - 1] - DP[N - 1][j - 1] 로도 구해진다. 따라서 2 중 for 문으로도 표현할 수 있다. 코드..

풀이 2 자리수 부터 생각해보면 다음과 같다. 1 --> 0, 22 --> 1, 33 --> 2, 4...9 --> 8 3 자리수는 다음과 같다. 0 --> 11 --> 0, 1...8 --> 7, 99 --> 8 이렇게 살펴보면, 3 자리수 부터 다음의 규칙이 적용된다는 것을 알 수 있다. 1. 0 이 나오면 다음 수는 1 이 와야한다.2. 9 가 나오면 다음 수는 8 이 와야한다.3. 1 ~ 8 의 다음 수는 각각 2개가 있다. 이 규칙을 그림으로 그려보면, 점화식을 생각해 낼 수 있을 것 이다. 위 표에서 열은 해당 자리수의 마지막 수를 나타낸다. 그리고 값의 자리는 해당 자리수의 각각의 마지막 수가 나오는 경우의 수다. 그렇다면 이제 위 표를 DP 배열로 나타내고 입력받은 N 자리수에 대한 해당 ..

개요 이 문제는 이전 타일링 문제들과 아주 유사한 방식으로 풀어낼 수 있다. 이전 두 문제의 연습결과 쉽게 풀어낼 수 있었다. 마찬가지로 유념해야할 점은 규칙을 찾아내야 한다는 것이다. 풀이 어떤 수 N 을 1, 2, 3 으로 더하는 총 개수를 구해야 한다. 이전 문제들과 유사하게 이미 구한 값을 사용한다는 개념을 보면 규칙이 보인다. 4 의 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 2 + 1 + 1 2 + 2 3 + 1 로 총 7가지의 경우의 수가 존재하는데 이것은 다음과 같이 바꿔서 볼 수 있다. 1 + (N - 1 을 1, 2, 3 으로 나타내는 경우의 수) 2 + (N -2 를 1, 2, 3 으로 나타내는 경우의 수) 3 + (N - 3 을 1, 2, 3 으로 ..

개요 이 문제는 11726 문제 (2xn 타일링) 의 다른 버전이다. 11726 문제를 정확히 이해했다면 같은 방식으로 풀어낼 수 있다. 풀이 2 x n 타일링 문제에서는 2 x n 타일을 채우기 위해 1 x 2, 2 x 1 타일을 사용했다. 그러나 이 문제에서는 2 x 2 타일이 추가되었다. 무엇이 달라질까? (1) 2 x 1 (2) 2 x 2 2 x 1 과 2 x 2 를 위와같이 준비해놓았을 때 2 x 3 은 다음과 같이 그릴 수 있다. (3) 2 x 3 2 x 2 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 크기의 타일을 세로로 하나 넣는다. ---> 개수 변화 없음. 2 x 1 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 번 크기의 타일을 가로로 2개 넣는다. ---> 개수가 x 2 가..