해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 1463번 1로 만들기 - dp

https://www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
 2. X가 2로 나누어 떨어지면, 2로 나눈다.
 3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

1.DP(동적계획법)을 이용해 풀 수 있는 문제입니다. DP[N]은 N이 1로되는 최소값을 넣어주면 됩니다.

2.처음 두 수를 알기 때문에 상향식으로 풀면됩니다.

3.N이 3으로 나누어 지면, DP[N//3]+1을 하면 만들 수 있습니다.

  N이 2로 나누어 지면, DP[N//2]+1을 하면 만들 수 있습니다.

  DP[N-1] + 1로 구합니다.

4. 위 3가지 경우 최소의 값을 DP[N]에 넣어줍니다.

전체 코드

n = int(input())
dp = [0 for i in range(n+2)]

dp[1] = 0
dp[2] = 1

for i in range(3,n+1):
    dp[i] = dp[i-1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
print(dp[n])

파이썬 / BOJ 백준 / 2579번 계단 오르기 - dp

https://www.acmicpc.net/problem/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

풀이

1. dp로 풀 수 있는 문제입니다.

2. 각 계단의 점수는 입력을 받아와 리스트 s에 넣습니다. (s[0]을 첫번째 계단으로 생각합니다.)
1차원 dp를 만들고, dp의 첫번째에는 s[0]을 넣습니다.
두번째 칸은 첫번째 칸을 통해서 올 수 밖에 없기 때문에 dp의 두번째에는 s[0] + s[1]을 넣어줍니다.

3. dp[n]은 직전 칸에서 올라온 경우와, 전전 칸에서 올라온 경우가 있습니다. 이 두 가지 경우의 최대값을 넣어줍니다. 그러면 dp에는 각 층까지의 최대값이 누적되어 들어가게 됩니다.

4. 직전칸에서 올라온 경우(n-1)는 전전 칸(n-2)에서 올라올 수 없으니, 그 전칸(n-3)에서 올라 올 수 있습니다. 식으로 만들면 dp[n-3] + s[i-1]로 표현할 수 있습니다.

5. 전전 칸에서 올라온 경우는 dp[n-2]로 표현할 수 있습니다.

6. 이를 식으로 만들면 dp[i] = max(dp[i - 3] + s[i - 1] , dp[i - 2]) + s[i]로 표현할 수 있습니다.

전체 코드

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    s[i] = int(input())

dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] , dp[i - 2]) + s[i]
print(dp[n - 1])

파이썬 / BOJ 백준 / 1932번 정수 삼각형 - dp

https://www.acmicpc.net/problem/1932

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

풀이

1. dp로 풀 수 있는 문제입니다.
2. 위 층의 값들을 아래층의 값에 합산해 갈 수 있는데, 합산하는데 3가지 case가 있습니다.
3. 첫번째 케이스는 j = 0일 경우 아래층의 값은 바로 위층의 값을 가져와 합산합니다.
dp[i][j] + dp[i - 1][j]
4. 두번째 케이스는 i = j일 경우 아래층의 값은 왼쪽 대각선 위층의 값을 가져와 합산합니다.
dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
5. 세번째 케이스는 나머지 조건일 경우 아래층의 값은 바로 위층의 값과 왼쪽 대각선 위층의 값중 큰 값을 가져와 합산합니다.
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j]

6. 마지막으로 맨 아래층의 값 중 가장 큰값을 출력합니다.

전체코드

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))
k = 2
for i in range(1, n):
    for j in range(k):
        if j == 0:
            dp[i][j] = dp[i][j] + dp[i - 1][j]
        elif i == j:
            dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j]
    k += 1
print(max(dp[n - 1]))

파이썬 / BOJ 백준 / 1149번 RGB 거리 - dp

https://www.acmicpc.net/problem/1149

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

풀이

1. dp는 각 색상에 대하여 누적 최소값을 나타냅니다.

2. 첫번째의 dp[0][0], dp[0][1], dp[0][2]의 값은 각각 빨간색, 초록색, 파란색의 첫번째 값을 넣어줍니다.

3. 2번째 값부터는 집이 연속된 색상을 가지지 말아야 합니다. 그래서 빨간색 집의 dp는 현재 빨간색의 집 칠하는 비용과 이전의 초록색 집의 dp와 파란색 집의 dp 중 작은 값을 넣어 줍니다.
그러면 red[n] + min(dp[n-1][1] , dp[n-1][2]) 와 같은 식이 만들어 집니다.

4. 초록색 집의 dp와 파란색 집의 dp도 이와 유사하게 구합니다.

5. 이렇게 구해진 값 dp[n][0], dp[n][1], dp[n][2] 중 최소값을 선택하면 됩니다.

전체 코드

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))
for i in range(1, len(dp)):
    #print(dp[i][0], dp[i][1], dp[i][2])
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + dp[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + dp[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + dp[i][2]
    #print("sum : ", dp[i][0], dp[i][1], dp[i][2])
print(min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))