✅ 문제 풀이 - DP
🎈 9095 1,2,3 더하기
테스트케이스 t와 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오
import sys
input = sys.stdin.readline
def plus(n):
if dp[n] > 0:
return dp[n]
if n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4
else:
dp[n] = plus(n-3) + plus(n-2) + plus(n-1)
return dp[n]
t = int(input())
for _ in range(t):
n = int(input())
dp = [0]*(n+1)
print(plus(n))< 풀이 과정 >
n값에 따른 dp의 결과를 입력해주기 위해 plus라는 함수를 새로 만들어주었다.
for문으로 t회 반복하며 n을 입력받고 plus(n)의 결과를 출력하는 문제
🎈 9465 스티커
스티커를 2n개 구매하였고 2행 n열로 스티커는 배치되어있다.
첫 줄에 테스트케이스 t가 주어지고 각 테케의 첫 줄에는 n이 주어지고 다음 2줄에는 n개의 스티커 점수가 주어진다. 이때 스티커를 떄면서 최대 점수의 합을 구하고자 하는데, 스티커를 떄게 되면 뗀 스티커의 위, 아래, 왼쪽, 오른쪽은 사용할 수 없게 되어 점수가 0이 된다.
스티커를 떼가면서 뗀 스티커 점수의 최대값을 구하는 문제
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
sticker = []
for i in range(2):
sticker.append(list(map(int, input().split())))
for j in range(1, n):
if j == 1:
sticker[0][j] += sticker[1][j-1]
sticker[1][j] += sticker[0][j-1]
else:
sticker[0][j] += max(sticker[1][j-1], sticker[1][j-2])
sticker[1][j] += max(sticker[0][j-1], sticker[0][j-2])
print(max(sticker[0][n-1], sticker[1][n-1]))< 풀이 과정 >
스티커를 뗀 정수의 값을 더해주기 위해선 대각선 방향만 값을 더해서 확인해주면 된다.
for 문으로 t회 반복하는 동안 n과 sticker 리스트를 입력받는다. (sticker의 경우 2행이므로 for문으로 2회 반복하여 append 진행)
이후, n열까지의 값을 비교하기 위해 for문으로 1~n-1까지 반복해준다.
sticker[0]은 0행, sticker[1]은 1행으로 값을 저장해놓고 서로 대각선으로 cross하며 값을 합산한다. 이후 2부터 n열까지는 이전 값과 두번째 전의 값을 비교하여 더 큰 값을 넣어주는 식으로 값을 더해주면 된다.
🎈 1520 내리막길
세로m, 가로n이 주어지고 다음 m줄의 걸쳐 한 줄의 n개씩 각 지점의 높이가 주어진 상황에서 왼쪽 제일 위에서 오른쪽 제일 아래칸으로 이동하려고 할 때 내리막길로만 이동하는 경우의 수를 구하는 문제
import sys
input = sys.stdin.readline
# 세로, 가로 입력, 방문한 곳 여부 판단
m, n = map(int, input().split())
visited = [[-1]*n for _ in range(m)]
# 상하좌우 4방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
graph = []
for _ in range(m):
graph.append(list(map(int, input().split())))
def dfs(x, y):
# 도착지점 도착 시 한 가지 경우 리턴
if x == m-1 and y == n-1:
return 1
# 이미 방문한 곳이라면 그 위치에서 출발하는 경우로 볼 것
if visited[x][y] != -1:
return visited[x][y]
route = 0
# 상하좌우 4방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 주어진 범위, 내리막길 조건 만족 시
if 0<=nx<m and 0<=ny<n and graph[x][y] > graph[nx][ny]:
route += dfs(nx, ny)
visited[x][y] = route
return visited[x][y]
print(dfs(0, 0))< 풀이 과정 >
이동하는 모든 경우의 수를 구하는 문제가 아닌 중간에 겹치는 길이 있으면 한 경로로 봐야하는 문제이다.
따라서 dfs를 이용하여 구현하였는데 작동방식은 다음과 같다
1. dfs 탐색을 진행해 현위치가 도착지점이면 1가지 경로이므로 1을 리턴
2. 이미 방문한 곳이라면 해당 위치에서 출발하여 탐색 진행하기. (모든 경로를 찾는 경우의 수 문제가 아니므로 반드시 해당 조건 걸어주기, 즉 memoization을 의미)
3. 상하좌우 4방향으로 탐색을 진행하며 이미 방문한 곳이면 route += dfs(nx, ny)로 해당 visited값을 그대로 반환하고 방문한 곳이므로 다음 위치를 바로 탐색하도록 다음 위치 값을 route에 더해주고 현 위치를 방문한 값을 route로 저장 하여 리턴해준다.
