문제
남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.
이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.
철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.
돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?
입력
첫 번째 줄에 돌의 개수 N이 주어진다.
두 번째 줄에 돌의 높이 가 서쪽부터 동쪽으로 차례로 주어진다.
입력은 다음 조건을 만족한다.
인 정수
인 정수
출력
첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.
예시
입력
5
3 2 1 4 5
Plain Text
복사
출력
3
Plain Text
복사
정답
import sys
N = int(sys.stdin.readline())
rock_list = list(map(int, sys.stdin.readline().split()))
dp = [1]*N # 해당 돌 위치에서 끝나는 경우 최대 밟을 수 있는 돌의 개수 -> let 돌 계수
for i in range(1,N):
for j in range(i): # 해당 돌 위치보다 이전 돌들을 하나씩 살펴봄
if rock_list[i] > rock_list[j]: # 만약 현재 돌 위치보다 낮은 위치의 돌이라면
dp[i] = max(dp[i], dp[j]+1) # 현재 돌 계수보다 그 돌의 계수 + 1이 더 크다면 돌 계수 업데이트
print(max(dp)) # 가장 큰 돌의 계수 print
Python
복사
풀이
•
동적계획법을 활용하는 문제이다.
•
포인트는 각 돌의 위치에서 끝날 때 최대 밟을 수 있는 돌의 개수를 구하는 것이다.
•
예를 들어 예시에서 첫 번째 돌에서 끝나는 경우 최대 밟을 수 있는 돌의 개수는 당연히 한 개이며 두 번째 돌에서 끝나는 경우 3을 밟을 수는 없으므로 마찬가지로 한 개이다.
•
이를 돌의 계수라고 하자.
•
돌의 계수는 최소 1부터 시작한다.
dp = [1]*N # 해당 돌 위치에서 끝나는 경우 최대 밟을 수 있는 돌의 개수 -> let 돌 계수
Python
복사
•
그리고 현재 돌의 계수는 현재 돌보다 이전 돌이며 돌의 높이가 더 낮은 돌들 중에서 최대인 계수에 1을 더한 값이다.
•
왜냐하면 그 이전에 최대로 돌을 밟고 현재 돌을 밟아야(+1) 하기 때문이다.
•
따라서 현재 이전의 돌들 중에서 돌의 높이가 더 낮은 돌을 찾고 그 돌의 계수 +1 이 현재 돌의 계수보다 크거나 같으면 그것을 현재 돌의 계수로 업데이트 해준다.
•
참고로 첫 번째 돌의 계수는 1이 확정이므로 두 번째 돌부터 탐색을 해주면 된다.
for i in range(1,N): # 두 번째 돌부터 탐색
for j in range(i): # 해당 돌 위치보다 이전 돌들을 하나씩 살펴봄
if rock_list[i] > rock_list[j]: # 만약 현재 돌 위치보다 낮은 위치의 돌이라면
dp[i] = max(dp[i], dp[j]+1) # 현재 돌 계수보다 그 돌의 계수 + 1이 더 크다면 돌 계수 업데이트
Python
복사
•
마지막으로 돌의 계수의 MAX값을 출력하면 최대 밟을 수 있는 돌의 개수이다.
print(max(dp)) # 가장 큰 돌의 계수 print
Python
복사