[Baekjoon/백준] 1932번 Python

문제 출처: www.acmicpc.net/problem/1932

1932번: 정수 삼각형

1. 문제 접근 방식

- 위에서 밑으로 내려가면서 계속해서 값을 대체하는 방법을 이용해야 겠다고 생각하였다. 양 끝의 숫자들은 하나의 경우만 고려하면 되는데 가운데 있는 숫자들은 두 가지 중 큰 수를 골라야 했다. 하지만 파이썬은 max()함수가 있다!

 

2. 내가 푼 코드

import sys

n = int(sys.stdin.readline())

num = []
s = 2

for i in range(n):
    num.append(list(map(int, sys.stdin.readline().split())))

# 가장 왼쪽, 오른쪽, 중간으로 범위를 나눠서 계산한다
# 가장자리에 있는 경우는 더할 숫자가 정해져 있어 인덱스 계산만 잘해서 더하면 됨
# 중간에 있는 숫자의 경우 오른쪽 위, 왼쪽 위의 값 중 최대값을 구하여 더함
for j in range(1, n):
    for k in range(s):
        if k == 0:
            num[j][k] = num[j][k] + num[j-1][k]
        elif j == k:
            num[j][k] = num[j][k] + num[j-1][k-1]
        else:
            num[j][k] = num[j][k] + max(num[j-1][k-1], num[j-1][k])
    s += 1

print(max(num[n-1]))

 

3. 결과 및 느낀점

- 성공! 백준의 문제들을 풀다보니 티어의 개념이 있다는 것을 알게되었다. 현재 4월 9일 기준 실버3이다. 첫번째 목표는 골드5를 찍는 것이다. 힘내자!