Python을 이용한 11048번 : 예산에 대해서 포스팅하겠습니다. 11048번은 다이나믹 프로그래밍로 분류되는 문제입니다.
1. 11048번 문제설명
- 입력
- N과 M: N×M 크기의 미로. N과 M은 각각 1 이상 1,000 이하입니다.
- 미로 정보: 각 칸에는 사탕이 놓여 있으며, 사탕의 개수는 0 이상 100 이하입니다.
- 목표
- 시작 위치는 (1, 1)이고, 목표 위치는 (N, M)입니다.
- (1, 1)에서 출발하여 (N, M)까지 이동하면서 방문한 각 방의 사탕을 모두 수집합니다.
- 준규는 다음 위치로만 이동할 수 있습니다:
- 아래로 한 칸 (r+1, c)
- 오른쪽으로 한 칸 (r, c+1)
- 대각선 아래 오른쪽으로 한 칸 (r+1, c+1)
- 출력
- 준규가 (N, M) 위치에 도달했을 때 수집할 수 있는 사탕의 최대 개수를 출력합니다.
2. 11048번 접근방법
- 문제 해결을 위해 동적 계획법(Dynamic Programming)을 사용합니다.
- 각 칸에 대하여 해당 칸에 도달할 때까지 수집할 수 있는 최대 사탕 수를 저장하는 배열을 유지합니다.
3. 11048번 구현
- 기본 설정: (1, 1) 위치의 사탕 수는 초기 설정값입니다.
- 전개: 배열의 각 칸을 순회하면서 다음을 고려합니다:
- 첫 번째 행과 첫 번째 열은 바로 이전 칸의 값을 이용해 갱신합니다.
- 그 외의 칸은 위쪽, 왼쪽, 왼쪽 위 대각선에서 올 수 있는 칸의 값들 중 최대값을 현재 칸의 사탕 수와 합산하여 최대 사탕 수를 갱신합니다.
- 결과: 마지막 칸, 즉 (N, M) 위치의 값이 준규가 수집할 수 있는 최대 사탕 수입니다.
- 효율성
- 이 문제는 N과 M의 최대 크기가 각각 1,000이기 때문에, 최대 1,000,000개의 칸을 처리해야 합니다.
3-1. 11048번 코드
Python
# https://www.acmicpc.net/problem/11048
from sys import stdin
# 미로의 크기 N과 M을 입력 받습니다.
n, m = map(int, stdin.readline().split())
# 미로의 각 칸에 놓인 사탕 수를 입력 받아 2차원 배열로 저장합니다.
nums = list(map(lambda a: list(map(int, a.split())), stdin.readlines()))
# 이중 반복문을 사용하여 미로의 모든 칸을 순회합니다.
for i in range(n):
for j in range(m):
# (1, 1) 위치는 시작 위치로, 여기서의 사탕 개수는 이미 초기 값으로 설정되어 있습니다.
if i == 0 and j == 0:
continue
# 첫 번째 행의 칸들은 왼쪽에서 오른쪽으로만 이동 가능합니다.
# 따라서 왼쪽 칸에서 오는 것만 고려합니다.
if i == 0:
nums[i][j] += nums[i][j-1]
continue
# 첫 번째 열의 칸들은 위에서 아래로만 이동 가능합니다.
# 따라서 위쪽 칸에서 오는 것만 고려합니다.
if j == 0:
nums[i][j] += nums[i-1][j]
continue
# 그 외의 경우, 준규는 (r+1, c), (r, c+1), (r+1, c+1) 세 방향으로 이동할 수 있습니다.
# 이 중에서 사탕 수가 최대가 되는 방향을 선택합니다.
# max 함수를 사용하여 세 방향 중 최대 사탕 수를 현재 칸에 더합니다.
nums[i][j] += max(nums[i-1][j], nums[i][j-1], nums[i-1][j-1])
# 결과로 (N, M) 위치의 최대 사탕 수를 출력합니다.
print(nums[-1][-1])