이번 주를 DP의 주간으로 명명하고 스터디원들과 DP문제만 뿌셔보기로 했다.
DP문제를 풀이하면서 풀이 영상이나 풀이법들을 보면 → 2차원 배열을 사용하는 경우가 많다.
그래서 이번 문제를 풀면서 나의 의식의 흐름도 자연스럽게
이 문제는 얼핏보면 간단한데, 결국 문제의 핵심은
연속으로 3개의 계단을 밟으면 안된다!!
이다.
연속으로 계단을 밟아도 된다면, 모든 계단을 밟아서 도달하는 쪽이 가장 점수가 높을 테니까,
DP로 문제를 풀면서 점화식을 생각해보면서, 역으로(맨 마지막에서 → 처음으로) 생각해 보는 경우가 많아진다.
예를 들어 이 그림에서 마지막 ‘도착’ 까지 가는 경우의 수를 생각해보자.
- 연속으로 3칸을 밟지 못한다고 하였으므로 15까지 오는 경우 → 10을 밟고 → 마지막 칸에 도달
- 25까지 오는 경우 → 2칸을 밟아서 마지막 칸에 도달
⇒ 결국 이 2가지 케이스인 것을 확인할 수 있다.
ex) 마지막 칸에 도달하는 경우의 수
- 15까지 오는 경우의 수 + 10밟고 + 1칸가서 10
- 25까지 오는 경우의 수 + 2칸가서 20나는 계단의 높이를 닮은 stairs 배열과, 각 칸에 도착했을 때 가장 높은 점수를 계산하기 위한 stair_list라는 이차원 배열을 만들어 주었다.
# stairs = [0, 10, 20, 15, 25, 10, 20]
# stair_list
# j = 0, 1, 2, 3, 4, 5, 6
# |0|10|20|15|25|10|20|
# 10| 0 10 30 35 50 65 65
# 20| 0 0 20 25 55 45 75처음 코드
import sys
N = int(sys.stdin.readline().rstrip())
stairs = [0]
for _ in range(N):
stairs.append(int(sys.stdin.readline().rstrip()))
stair_list = [[0]*(N+1) for _ in range(2)]
def walk(n):
for i in range(2):
for j in range(n+1):
if j == 0:
stair_list[i][j] = 0
# i번째 칸에 오르는 방법-1 : n-3번째 칸에오른뒤 -> n-1번째 칸을 밟고 -> n번째 칸을 밟는 것
if i == 0:
if j < 3:
stair_list[i][j] = max(stair_list[0][j-1], stair_list[1][j-1]) + stairs[j]
elif j >= 3:
stair_list[i][j] = max(stair_list[0][j-3], stair_list[1][j-3]) + stairs[j-1] + stairs[j]
# i번째 칸에 오르는 방법-2 : n-2번째 칸에 오른뒤 -> n번째 칸을 밟는 것
elif i == 1 and j > 1:
stair_list[i][j] = max(stair_list[0][j-2], stair_list[1][j-2]) + stairs[j]
return(max(stair_list[0][n], stair_list[1][n]))
print(walk(N))
이렇게 제출했더니 7% 에서 ‘틀렸습니다’ 가 나왔다!
→ 그리고 나의 안좋은 습관 (게시판 쥐잡듯이 검색해서 맞왜틀… 거리면서 반례검색하기) 가 다시 시작되었다.
→ 아무리 찾아봐도 반례가 다 돌아가는데, 내 logic에도 틀린게 없는 것 같은데? 라고 생각하던 중 디버깅을 돌리면서 한가지가 생각났다.
어라라? 이거 한 행이 끝나고 다음행으로 넘어가잖아?
그렇다. 위의 코드대로 진행하면 1칸씩 올라가는 방법을 다 구하고~ 그 다음 2칸씩 올라가는 방법을 구하게 된다. 위의 예시는 우연히도! 넘어갈 수 있지만, 이렇게 구하면 안된다는 것을 알겠다.
즉, i번째칸이라고 했을 때 i번째 칸에 오르는 2가지 방법을 다 검사하고 → 그 다음 칸으로 넘어가는 방식을 채택해야겠구나! 라는 생각을 했다.
열 우선 탐색으로 for문을 바꾸면 되겠구나!
해결책은 간단하다. 행우선 탐색(i)를, 열우선 탐색(j)로 바꾸주면 되는 것!
최종코드
import sys
N = int(sys.stdin.readline().rstrip())
stairs = [0]
for _ in range(N):
stairs.append(int(sys.stdin.readline().rstrip()))
stair_list = [[0]*(N+1) for _ in range(2)]
def walk(n):
for j in range(n+1):
for i in range(2):
if j == 0:
stair_list[i][j] = 0
# i번째 칸에 오르는 방법-1 : n-3번째 칸에오른뒤 -> n-1번째 칸을 밟고 -> n번째 칸을 밟는 것
if i == 0:
if j < 3:
stair_list[i][j] = max(stair_list[0][j-1], stair_list[1][j-1]) + stairs[j]
elif j >= 3:
stair_list[i][j] = max(stair_list[0][j-3], stair_list[1][j-3]) + stairs[j-1] + stairs[j]
# i번째 칸에 오르는 방법-2 : n-2번째 칸에 오른뒤 -> n번째 칸을 밟는 것
elif i == 1 and j > 1:
stair_list[i][j] = max(stair_list[0][j-2], stair_list[1][j-2]) + stairs[j]
return(max(stair_list[0][n], stair_list[1][n]))
print(walk(N))이렇게 제출했더니 시원하게 맞았습니다!! 가 나왔다.
A형 탈락이후에 코드를 한 번더 꼼꼼하게 보는 습관을 기르려고 한다.
한방에 맞도록 짜기! 기억하자.
Uploaded by N2T