내일이면 파이썬 방학 캠프가 끝이 나네요. 마지막은 마무리 시험을 보며 끝이 납니다. 2주밖에 되지 않았지만 파이썬 수업을 한 번도 들어보지 않은 입장으로 정말 익숙해졌다고 생각해요. 알고리즘 쪽으로나 구현 쪽으로나 파이썬과 친해진 게 느껴집니다. 아주 만족합니다. 오늘은 마지막으로 동적 계획법 문제를 하나 가져왔습니다. 코드 트리를 주제로는 마지막 포스팅이 될 수도 있겠네요.
문제
행렬이 주어졌을 때, 에서 시작하여 오른쪽 혹은 밑으로만 이동하여 간다고 했을 때 거쳐간 위치에 적혀있는 숫자들 중 최솟값을 최대로 하는 프로그램을 작성해보세요.
입력 형식
첫째 줄에는 이 주어집니다.
두 번째 줄부터 N개의 줄에 각각 각 행에 해당하는 개의 정수 값이 공백을 사이에 두고 주어집니다.
- 행렬에 주어지는 숫자
출력 형식
가능한 경로의 숫자들 중 최솟값의 최댓값을 출력합니다.
입출력 예제
예제 1
입력:
3
5 2 3
3 2 1
1 2 4
출력:
2
예제 2
입력:
3
4 3 2
3 4 5
4 2 8
출력:
3
예제 설명
첫 번째 예제의 경우 다음과 같이 이동하면 지나는 경로에 적혀있는 숫자들 중 최솟값이 가 되며, 더 크게 답을 만들 수가 없습니다.

처음에 보면 뭔 소리인지 잘 몰랐는데요 1,1에서 n, n까지 가는데 모든 경로가 있겠죠? 그 경로도 하나의 최솟값을 가지고 있을 겁니다 그 모든 경로의 최솟값만 모아 놨을 때 그 최솟값 속에 가장 큰 수는 무엇인가 하는 문제입니다.
코드
n = int(input())
nums = [
list(map(int,input().split()))
for _ in range(n)
]
dp = [[0 for _ in range(n)]for _ in range(n)]
#가는 경로중 무조건 최소값이 있을텐데 그 최소값중 가장 큰것은 무엇인가?
def init():
dp[0][0]=nums[0][0]
for i in range(1,n):
dp[i][0] = min(dp[i-1][0], nums[i][0])
dp[0][i] = min(dp[0][i-1], nums[0][i])
init()
for i in range(1,n):
for j in range(1,n):
dp[i][j] = min(max(dp[i-1][j] , dp[i][j-1]), nums[i][j])
print(dp[n-1][n-1])
'Knowledge > Python' 카테고리의 다른 글
[백준] 2178번: 미로 탐색 Python 코드, BFS (6) | 2022.10.14 |
---|---|
[코드트리] 두 방향 탈출 가능 여부 판별하기 , python 문제 풀이 (4) | 2022.07.25 |
[코드트리] 금 채굴하기 , python 문제 풀이 (8) | 2022.07.18 |
[코드트리] 가운데에서 시작하여 빙빙 돌기 ,python 문제 풀이 (4) | 2022.07.17 |
[코드트리] 거울에 레이저 쏘기 2 ,python 문제 풀이 (2) | 2022.07.17 |