[백준] DP <2>
DP에 대한 설명은 이하 링크를 참고
DP <1>
# 1904 01타일
이번 문제는 “00” 타일과 “1” 타일을 가지고 전체 길이가 N인 2진수의 갯수를 세는 문제이다.
예를 들어
N = 1 인 경우 1 만 가능하다. f(1) = 1
N = 2 인 경우 11과 00이 가능하다. f(2) = 2
N = 3 인 경우 100, 001, 111 이 가능하다. 010의 경우 “00” 타일을 나누는 것이 되기 때문에 불가능하다. f(3) = 3
N = 4 인 경우 0000, 1100, 1001, 0011, 1111 이 가능하다. f(4) = 5
이렇게 작성했을때, 결과를 자세히 보면 피보나치 수열이 된다. 하지만 그것보다 이 점화식이 어째서 피보나치 수열을 띄는지가 중요할 것이다.
N = 4 인 경우를 예를 들어보자면 1100, 0011, 1111 은 N = 3 인 경우의 수에서 “1” 타일을 추가한 결과이다.
또한 0000, 1001은 N = 2인 경우의 수에서 “00” 타일을 추가한 결과가 된다.
N = 5을 살펴보자. N = 5의 경우
10000, 00100, 00001, 10011, 11001,11100, 00111, 11111 로 8개이다.
이때 11001, 10011, 11111, 10000, 00111은 N = 4인 경우의 수에서 “1” 타일을 추가한 결과이다.
10000, 00001, 11100은 N = 3인 경우의 수에서 “00” 타일을 추가한 결과이다.
즉 피보나치 수열과 같은 점화식을 사용하는게 가능하다.
$f(N) = f(N-1) + f(N-2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
number = int(sys.stdin.readline().strip())
def zeroOneTile(num,list = [1,1]):
if (num == 0 or num == 1):
return 1 % 15746
else:
for i in range(2, num+1):
list.append((list[i-1] + list[i-2])%15746)
return list[num]
print(zeroOneTile(number))
문제에서는 숫자가 너무 커질 경우를 대비해 15746으로 나눈 나머지의 값을 요구하고 있다.
# 1149 RGB 거리
백준에서 단계적으로 풀어보기를 순서대로 풀다 보면 처음으로 접할 수 있는 2차원 DP를 활용하는 문제이다.
문제는 유명한 4색정리와 유사하다. 인접한 집 끼리 같은 색으로 칠하지 않아야 하며 색은 총 RGB 3개가 주어진다.
이때 각 집마다 RGB 각각의 색에 대한 칠하는 cost가 주어지고 모든 집을 칠했을 경우의 최소 cost를 찾아내는 문제이다.
문제의 예시를 들어 설명하자면 집이 3개 주어졌을때 각각 집에 대한 색의 cost가 주어진다.
26 40 83
49 60 57
13 89 99
이때 문제의 조건을 어기지 않고 최소한의 비용으로 색을 칠하는 경우는 첫번째 집을 26, 두번째 집을 57, 세번째 집을 13으로 칠해 총 96의 비용이 나오는 경우이다.
이 문제를 2차원 dp를 활용해 풀어보자.
2차원 dp를 활용한 풀이
먼저 주어진 비용들을 표로 만들어 사용한다.
R G B 26 40 83 49 60 57 13 89 99 첫 행은 고정한 후 다음 행부터 비용이 최소가 되는 경우의 수를 기록한다.
즉 2번째 집을 R로 칠하고 싶은 경우엔 첫 집이 G 혹은 B 여야 할 것이다. 이때 2번째집 + min(첫번째가 G, 첫번째가 B)를 계산한 후 dp에 기록한다. 2번째 집의 나머지 색의 경우도 같다. 그렇게 해서 표를 다시 작성하면…
R G B 26 40 83 49 + min(40, 83) = 89 60 + min(26, 83) = 86 57 + min(26, 40) = 83 13 89 99 다음으로 나오는 행들에 대해서도 같은 과정을 적용해주면 된다.
R G B 26 40 83 89 86 83 13 + min(86, 83) = 96 89 + min(89, 83) = 172 99 + min(89,86) = 185 전체 행(= 모든 집)에 대해 이 과정을 수행해 준 후, 마지막 행의 값 중에서 가장 작은 값이 답이 된다.
이때 마지막 행의 의미는 주어진 조건(인접한 집과 다른 색이어야 함)을 만족하면서 마지막 집을 해당 색으로 칠했을 때 가장 작은 값이 나오는 결과들이다.
이 과정을 코드로 작성한다면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
import sys
read = sys.stdin.readline
houseCount = int(read())
costs = [list(map(int, read().split())) for _ in range(houseCount)]
# 반복문에서 각 단계별로 이전에 고른 색에 대한 최소값을 모두 더한후 저장해둠.
for idx in range(1,houseCount):
costs[idx][0] += min(costs[idx-1][1], costs[idx-1][2]) # 이전에 red를 골랐을 경우
costs[idx][1] += min(costs[idx-1][0], costs[idx-1][2]) # 이전에 green을 골랐을 경우
costs[idx][2] += min(costs[idx-1][0], costs[idx-1][1]) # 이전에 blue를 골랐을 경우
print(min(costs[-1]))