문제
철수에게는 빨간색, 초록색, 파란색 세 개의 버튼이 있다. 버튼 하나를 누를 때 마다 특정 점수를 얻을 수 있으며, 철수는 1초에 한 번씩 버튼을 누를 수 있다. 물론, 특정 시간에는 세 개의 버튼 중에서 한 개의 버튼만을 누를 수 있다. 각 시간마다 특정 버튼을 눌렀을 때 얻는 점수는 모두 다를 수 있다. 예를 들어, 시간 1에 빨간색, 초록색, 파란색 버튼에 대한 점수가 3, 5, 7 로 주어질 수 있다. 이 경우에는 파란색을 누르는 것이 점수를 가장 많이 얻을 수 있다. 물론, 시간 2에 각 버튼에 대한 점수는 또 다를 수 있다. 버튼을 누를 때에는 한 가지 규칙이 있는데, 연속하여 색깔이 같은 버튼을 두 번 누를 수 없다는 것이다. 예를 들어, 시간 1에 초록색 버튼을 눌렀다면, 시간 2에는 초록색 버튼을 누를 수 없다. 이와 같은 규칙으로 각 시간마다 버튼을 누른다고 할 때, 철수가 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 철수에게 주어진 시간 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄부터 N개의 시간에 대하여 빨간색, 초록색, 파란색 버튼을 눌렀을 때 얻을 수 있는 점수가 주어진다.
출력
철수가 얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력
3
27 8 28
18 36 40
7 20 8
예제 출력
87
#풀이
우선 dp_table을 먼저 정의를 해야한다. 즉 점화식을 도출해내야 한다.
'''
세 개의 버튼 중에서 한 개의 버튼만을 누를 수 있다
연속하여 색깔이 같은 버튼을 두 번 누를 수 없다
철수가 얻을 수 있는 점수의 최댓값을 출력
'''
자세한 부분은 위의 문제를 참고 하면될 것이고, 점화식을 도출하는데 위의 3개의 단서를 통해 풀이를 이어나갈 것이다.
처음 얼핏보면 첫 행의 최댓값(27, 8, 28) : 28
두 번째 행의 최댓값(18, 36, 40) : 36 -- 40은 첫 행에서의 선택된 녀석과 버튼 색이 같아서 안된다.
세 번째 행의 최댓값(7, 20, 8) : 8
이렇게 해서 72가 나올 수도 있다.
이러고 출력 값을 보면 어 뭐지? 라는 생각이 들며 이렇게 저렇게 조합을 해본다.
그렇게 해보면 탐욕처럼 그 순간의 최선의 선택을 택하는 것이 아닌 전체가 최선인지를 봐야 한다는 규칙을 찾아낼 수 있다.
그러면 딱 봐서 여기서의 전체적인 최선은 뭔가 느낌상 일단 40이라는 숫자가 포함이 되는 루트로 흘러가면 어떨까? 라는 삘?이 온다. 그래서 한번 해보자. 두 번째 행에서 40을 택했다 전제를 하고 첫 행에서의 최댓값은 27이 된다.
그리고 세 번째 행에서의 최댓값은 20이 된다.
그렇게 해보니 "27+40+20"해서 87!!이 나온다.. 기쁨은 잠깐 이부분을 어떻게 표현할지 깊은 고민이 든다.
여기서부터 본격적으로 풀이를 해보면 우선 dp_table을 정의 해야한다.
여러 시행착오 끝에 나왔지만 결과만 적자면 dp_table의 정의는
"dp_table의 각자리수는 해당 해당 값과 해당 위치와는 다른 이전의 값 중 최댓값의 합이다."
이상한 헛소리를 좀 더 풀어 설명하면
입력 배열 arr = [[27 8 28], [18 36 40], [7 20 8]] 과 모양이 같은 dp_table을 만들어준다.
dp_table =[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
처음 27, 8, 28이라는 숫자를 만날 것이다.
여기서는 우리가 해줄 수 있는 것은 없다. 즉, 그냥 때려 밖자.
dp_table =[[27, 8, 28], [0, 0, 0], [0, 0, 0]]
그 다음 18, 36, 40
여기서 잘 생각해보자
인덱스가 0번째인 18이 왔다는 것은 이전에서 우리가 선택할 수 있는 인덱스는 0을 제외한 1, 2 두 가지의 경우가 존재하고 이중 우리가 관심있는 값은 최댓값이다. 18일 때 이전 요소를 살펴보면 8과 28이 있고 더 큰 값이 28을 선택해준다.
선택된 28과 해당 요소의 값인 18을 더해준다. 46
36도 마찬가지이다. 이전 행에서 가능한 인덱스는 0, 2번째인 27, 28이다. 여기도 28이 선택될 것이고, 64가 될 것이다.
그 다음 인덱스 2의 값인 40. 선택지는 인덱스 0, 1의 값이 27, 8이다. 27이 선택될 것이고 67이 된다.
dp_table =[[27, 8, 28], [46, 64, 67], [0, 0, 0]]
마지막도 위와 같은 패턴으로 하면
dp_table =[[27, 8, 28], [46, 64, 67], [74, 87, 72]]
이렇게 dp_table이 완성될 것이다.
dp_table에서 마지막 행의 값들이 최댓값이므로 이중 max값을 찾으면 답이된다.
그래서 핵심 로직이
dp_table[i][0] = arr[i][0] + max(dp_table[i-1][1], dp_table[i-1][2])
가 되는 것이다.
#코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
if __name__ == "__main__":
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp_table = [[0]*3 for _ in range(n)]
for i in range(n):
if i == 0:
dp_table[i][0] = arr[i][0]
dp_table[i][1] = arr[i][1]
dp_table[i][2] = arr[i][2]
else:
dp_table[i][0] = arr[i][0] + max(dp_table[i-1][1], dp_table[i-1][2])
dp_table[i][1] = arr[i][1] + max(dp_table[i-1][0], dp_table[i-1][2])
dp_table[i][2] = arr[i][2] + max(dp_table[i-1][0], dp_table[i-1][1])
print(max(dp_table[n-1]))
|
cs |