코딩테스트 문제풀이

문제풀이

1번

1932번: 정수삼각형

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

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

예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1
30

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

이 문제는 다이나믹 프로그래밍 문제로 삼각형의 맨 왼쪽의 경우 즉 array[i][0]일 경우 왼쪽 변이므로 왼쪽변의 상윗값만 더하는게 가능하다.
반대로 가장 오른쪽인 경우 오른쪽 변에 위치하므로 오른쪽 변의 상윗값만 더하는게 가능하다.
그 외에 가운데에 있는 숫자들은 결국 큰 수를 만들어야 하기 때문에 max()를 이용해서 두 수중 더 큰 수와 더한 값으로 변환한다.
그 다음 마지막 가장 아랫 리스트에서 가장 큰 수를 찾아서 프린트 해주면 된다.

문제2

11727번: 2xn 타일링2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

예제 입력 2
8

예제 출력 2
171

d = [0, 1, 3 ]
for i in range(3, 1001):
  d.append(d[i-1]+ 2*d[i-2])
n = int(input())
print(d[n]%10007)

가로 길이가 0일 경우 덮개가 필요 없기에 0, 가로 길이가 1인 경우 1x2 하나면 충분하기 때문에 1, 만약 가로 길이가 2인 경우 2x2 한개, 2x1 두개, 1x2 두개 총 3번의 방법이 존재하기 때문에 이 횟수들을 먼저 리스트 안에 넣어놓는다.
가로 길이가 i-1인 경우 가로길이가 2의 경우수 + 2x1 하나만 들어갈 수 있고 i-2인 경우 2x2 1개 1x2 두개가 들어가며 2x1 두개를 넣는 경우는 위의 경우에 포함되기 때문에 두번째 식에서는 더하지 않는다.

이를 리스트에 반복문을 통해서 하나씩 추가해주면 원하는 답을 찾을 수 있다.

문제 3

11048: 이동하기

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

예제 입력 1
3 4
1 2 3 4
0 0 0 5
9 8 7 6

예제 출력 1
31

n,m = map(int,input().split())
array=[]
for _ in range(n):
  array.append(list(map(int,input().split())))
# dp 만들기
dp = [[0] * (m + 1) for i in range(n + 1)]
#가장 큰 값을 찾아 더하는 과정
for i in range(1, n+1):
  for j in range(1, m+1):
    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+ array[i-1][j-1]
print(dp[n][m])

먼저 미로를 만들어 준다. 이 문제는 최대의 값을 찾아야 하는 문제로 사탕을 더하는 방법은 최대 3가지 이다.

이중에서 가장 큰 수를 찾기 위해 dp를 만들어 준다. dp의 크기는 미로의 크기보다 1행, 1열 더 크게 만들어 준다.

최대의 값을 구하기 위해서는 현재 항(dp[i][j])의 왼쪽(dp[i][j-1]) 위쪽(dp[i-1][j]) 왼쪽 대각선(dp[i-1][j-1]) 중 max()를 통해서 가장 큰 값을 찾은 후 미로의 현재항(array[i-1][j-1])을 더해준다.

array

1	2	3	4
0	0	0	5
9	8	7	6

dp의 최종 결과 값

0	0	0	0	0
0	1	3	6	10
0	1	3	6	15
0	10	18	25	31

위의 식대로 문제를 해결해보면 dp[1][1]의 경우 왼쪽과 왼쪽위 대각선 위쪽 모두 0이기 때문에 초기값 1이 들어서고 그 이후 항부터 크기 비교를 통해 큰 값과 array의 현재 값이 더해진 후 결국 최대값을 출력하게 된다.