끄적끄적

문제풀이

1. 배열 자료구조인 dp에 n번째 음식의 만족도를 담습니다. 즉, dp[i]는 i번째 음식의 만족도입니다.

2. 배열 자료구조인 dp2에는 n번째 음식을 먹었을 때의 만족도의 최댓값을 담습니다. 즉, dp2[i]는 i번째 음식을 먹었을 때의 만족도의 최댓값입니다.

3. dp2의 요소는 다음과 같은 과정을 통해 얻습니다.

3-1. n번째 음식의 인덱스를 n, 만족도를 nth라 할때, dp의 n번째 이전의 요소들 중 nth보다 작은 값들에 해당하는 dp2의 요소를 모읍니다.

3-2a. 위 과정에서 모은 요소들 중 최댓값+nth가 dp2[n]이 됩니다.

3-2b. 위 과정에서 모인 요소가 없다면, n번째 이전에 먹을 것이 없다는 의미이므로 dp2[n]은 nth가 됩니다.

** dp의 이름을 별 생각없이 dp로 지었는데, dp2가 실질적으로 메모리제이션이 이루어지는 배열이고, dp는 동적프로그래밍과 큰 관련이 없습니다.

Python Code

문제 링크

문제풀이

1. dp의 각 요소의 의미는 다음과 같다.

dp[0] : 입력 받은 칸을 red로 칠했을 때 코스트의 최솟값
dp[1] : 입력 받은 칸을 green로 칠했을 때 코스트의 최솟값
dp[2] : 입력 받은 칸을 blue로 칠했을 때 코스트의 최솟값

2. 현재 칸의 페인트의 코스트 r,g,b를 입력받았다면, 위의 관계를 아래와 같이 쓸 수 있다.

dp[0] = min(dp[1],dp[2])+r
dp[1] = min(dp[0],dp[2])+g
dp[2] = min(dp[0],dp[1])+b

Python Code

문제 링크

문제풀이

세 개의 요소를 활용한 dp로 문제를 풀겠습니다.

1. 배열 자료구조인 dp의 각 요소의 의미는 아래와 같습니다.

dp[n][0] : n번째 행의 왼쪽 칸에 사자가 있을 경우의 수.

dp[n][1] : n행의 오른쪽 칸에 사자가 있을 경우의 수.

dp[n][2] : n행에 사자가 없는 경우의 수.

2. 각 요소의 점화식은 다음과 같습니다.

2-1. dp[n][0] = dp[n-1][1]+dp[n-1][2] ; n행의 왼쪽에 사자를 넣기 위해서는 윗행의 오른쪽에 사자가 있거나(dp[n-1][1]) 윗행에 사자가 아예 없어야(dp[n-1][2]) 합니다.

2-2. dp[n][1] = dp[n-1][0]+dp[n-1][2] ; n행의 오른쪽에 사자를 넣기 위해서는 윗행의 왼쪽에 사자가 있거나 윗행에 사자가 아예 없어야 합니다.

2-3. dp[n][2] = dp[n-1][0]+dp[n-1][1]+dp[n-1][2] ; n행에 사자를 넣기 않으려면, 윗행에 사자가 어디에 있든 아예 없든 상관 없습니다.

3. dp의 요소가 너무 커지지 않도록 %9901을 해주며, n=1부터 입력받는 N까지 진행해준 후, sum(dp[n])%9901을 반환합니다.

Python Code

문제링크

문제풀이

1. $k_t$를 길이가 t이고 k로 끝나는 오르막 수라고 하고 점화식을 세우면 다음과 같습니다.

$k_t = \sum_{l=0}^k l_{t-1}$

즉, 길이가 2인 1로 끝나는 오르막 수의 개수는 길이가 1인 0으로 끝나는 오르막 수의 합(한개(0))과 길이가 1인 1로 끝나는 오르막 수의 합(한개(1))인 2개입니다. 0 뒤에 1을 붙이고, 1 뒤에 1을 붙여 {00, 01} 두 개가 됩니다.

2. 위의 $k$를 1부터 $n$까지 올리며 계산한 후, $\sum_{k=0}^9 k_n$을 반환합니다.

Python Code

Line 4, 6 : 문제의 조건에 따라 %10007을 해줍니다.

문제링크

문제 풀이

dp와 dfs를 함께 사용해야하는 문제이다.

1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.

2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.

  2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.

  2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.

  2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.

Python Code

Line 9 : 지도를 벗어나면 0을 반환한다.

Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).

문제 링크

문제 풀이

 스티커가 위와 같이 있다고 할 때, r번 행의 c번 열 스티커를 붙였을 때의 최댓값을 dp[r][c]라 하면, dp의 점화식은 아래와 같이 쓸 수 있다.

 r=0 인 경우 : dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]

 r=1 인 경우 : dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]

 위의 그림에서 a3를 붙였을 경우를 예로 들면, 스티커를 앞에서부터 붙인다면 a1, b1, b2를 붙인 다음에 a3를 붙이는 경우가 가능하다.

Python Code

Line 3 ~ 5 : Line 6의 for문으로 dp를 처리하는 과정에서 dp[r][i-2] 연산이 들어가므로 첫 번째, 두 번째 열(c=0,1)을 미리 처리해야 한다.

문제 링크

문제풀이

(r, c)까지 왔을 때 가질 수 있는 사탕의 최댓값을 dp[r][c]이라 하면, 점화식은 다음과 같이 쓸 수 있다.

dp[r][c] = max(dp[r][c-1], dp[r-1][c]

즉, (r,c) 까지 오는 방법은 같은 행의 왼쪽 열에서 오거나, 이전 행의 같은 열에서 오는 두가지 방법이 있다. 

따라서 모든 r을 0부터 n까지 반복한 후, dp[n][m]을 반환하면 된다.

Python Code

Line 4 : 첫번째 행에 대한 연산이다.

Line 6 : 두번째 행 이후에 대한 연산이다.

비효율적이었던 풀이

 풀이 설명을 보면 dp가 n*m 인 행렬이지만, 위의 코드는 길이가 m인 배열이다. 처음에는 maze 행렬을 모두 받아서 가진 상황에서 풀이를 했는데, 시간이 다른 풀이들에 비해 오래걸렸다. 좀 더 효율적으로 수정한 코드가 위의 코드이며, maze를 한줄씩 받으며 즉시 처리하는 식으로 바꿨더니 시간이 1632ms에서 720ms로 절반이상 줄었다. 메모리 역시 절반 이상 줄일 수 있었다.

 아래는 첫 풀이이다. 위의 코드와는 달리 bfs를 이용하여 0,0 부터 m,n까지 dp 행렬을 채워나갔으며, 위에서 말했듯, maze를 모두 받고 시작했고, dp는 모든 요소가 0인 m*n 행렬로 초기화하였다.

문제 링크

문제 풀이

 1. 간단한 dp 문제로, n번째 타일 장식물의 한 변의 길이 dp[n]에 대한 점화식은 다음과 같다.

 dp[n] = dp[n-1]+dp[n-2]

 2. 문제는 n번째 타일 장식물까지 붙였을 때, 가장 바깥의 둘레를 구하는 것인데, 예제에서 제시한 아래의 그림을 살펴보면, 계속 직사각형 형태를 띔으로 상하, 좌우의 길이는 각각 같다. 또한, 상하 또는 좌우의 길이 중 하나는 마지막 타일 장식물의 한 변의 길이가 되며, 나머지 한 변의 길이는 마지막 타일 장식물의 길이와 그 전 타일 장식물의 길이가 된다. 

예를 들면, 5개의 타일 장식물이 붙은 경우에는, 세로의 길이는 마지막 타일의 길이인 5 이고, 가로의 길이는 마지막 타일 장식물의 길이인 5에 이전 타일 장식물의 길이인 3을 더한 8이다. 6개의 타일 장식물을 붙였을 경우에는 가로가 8, 세로는 8(마지막 장식물의 길이)+5(이전 장식물의 길이) 인 13이 된다.

 따라서 n개의 타일 장식물을 붙였을 때의 둘레는 2*dp[n] + 2(dp[n]+dp[n-1]) 이 된다.

Python Code

문제 링크