백준 11048번: 이동하기
문제 설명
- (1,1)에서 (N,M)로 가야 합니다.
오른쪽으로 한 칸
,아래로 한 칸
,오른쪽 아래 대각선으로 한 칸
중 하나의 방법으로 움직일 수 있습니다.- 칸으로 이동하면 해당 칸에 적힌 숫자만큼 사탕을 얻습니다. 최대 몇 개의 사탕을 얻을 수 있는지를 구해야 합니다.
접근법
- 이 문제는
현재 칸에서 어디로 갈 수 있는가?
보다현재 칸으로 어떻게 올 수 있는가?
를 기준으로 생각하는 게 더 쉽습니다.
- 현재까지 모은 사탕의 개수는 이전 칸의 사탕 개수를 더해 표현할 수 있습니다.
위와 같이 사탕이 뿌려진 길을 빨간색 방향으로 왔다면 각 칸에서 가진 사탕의 총 량은 다음과 같습니다
즉 현재 칸까지 오면서 모은 사탕의 개수 = 이전 칸까지 오면서 모은 사탕의 개수 + 현재 칸의 사탕
이 성립합니다.
- 우리가 움직이는 방법이 3 가지 이기 때문에 특정 칸(☆)에 도달하는 방법도 3가지 입니다.
-
왼쪽에서 접근한다.
-
위에서 접근한다.
-
왼쪽 위에서 대각선으로 접근한다.
-
그렇다면 ☆에 최대한 많은 사탕을 가지고 접근하는 방법은 어떻게 될까요?
- 그건 ☆로 접근할 수 있는 3칸 중 사탕을 가장 많이 모은 곳에서 ☆로 오는 것입니다.
다음과 같다면 우리는 15에서 ☆로 가는 게 가장 현명한 방법일 것입니다.
- 우리는 1과 2의 방법을 모든 칸에 적용시키면 정답을 구할 수 있습니다.
만약 가장 많은 사탕을 모으는 방법으로 ☆에 도달하고,
마찬가지로 가장 많은 사탕을 모으는 방법으로로 ★에 도달했다면,
☆와 ★ 중 더 많은 사탕을 모은 곳에서 ?로 가는 게 가장 많은 사탕을 모으는 방법입니다.
정답
N,M = list(map(int,input().split(' ')))
#미로를 구현합니다
board = []
for _ in range(N):
board.append(list(map(int,input().split(' '))))
# (r+1,c),(r,c+1),(r+1,c+1)로 이동할 수 있다는 건 (x,y)에 (x-1,y),(x,y-1),(x-1,y-1)에서 도달할 수 있다는 걸 의미합니다.
direction = [[-1,0],[0,-1],[-1,-1]]
#모든 미로칸을 순회합니다
for i in range(N):
for j in range(M):
lst = [] # 3방향에서 들어오는 값을 비교하기 위해 일시적으로 lst라는 곳에 담아두겠습니다. 해당 변수는 미로칸이 바뀔때마다 초기화됩니다.
for d in direction:
id_ = i+d[0]
jd_ = j+d[1]
if 0<=id_<N and 0<=jd_<M: #미로를 벗어나지 않는 값들만 고려합니다
lst.append(board[id_][jd_])
if lst: #lst속에 값이 존재한다면
board[i][j] = board[i][j]+ max(lst) #해당 판으로 오면서 모을 수 있는 최대 사탕의 수 = 3가지 경우의 수 중 가장 많은 사탕을 모은 경우 + 해당 판에 놓인 사탕
print(board[N-1][M-1])
기타
- 문제가 복잡해질수록 글과 단편적인 그림만으로 설명하는게 어려운 거 같습니다.
- 문제를 푸는 것보다 설명을 고민하는 데 더 많은 시간을 사용했지만 설명이 만족스럽지 못합니다
- 최댓값을 구할 수 있는 경로를 출력해라고 한다면?
- 해당 칸마다 최대사탕의 정보와 해당 경로를 함께 저장하게 만들면 됩니다.
Author And Source
이 문제에 관하여(백준 11048번: 이동하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-11048번-이동하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)