BOJ 설탕배달, 정수삼각형

1. BOJ 2839 설탕배달

https://www.acmicpc.net/problem/2839

코드

N = int(input())
a = N//3
b = N//5
 
for i in range(N//5+1):
    if (N-5*b)%3==0:
        a = (N-5*b)//3
        break
    else:
        b-=1
if b==-1:
    print(-1)
else:
    print(a+b)

설명

3a + 5b = N이고, 이때 a+b이 최소가 되는 값을 구해야 한다. 

최대가 되는 b를 구하고 b를 1씩 줄여가며 값을 찾는다. 

 

2. BOJ 1932 정수삼각형

https://www.acmicpc.net/problem/1932 

코드

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
 
for i in range(1, N):
    for j in range(len(arr[i])):
        if j==0:
            arr[i][j] += arr[i-1][0]
        elif j==len(arr[i])-1:
            arr[i][j] += arr[i-1][-1]
        else:
            arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])
 
print(max(arr[-1]))

설명

RGB거리 문제를 풀고나니 접근하기에 훨씬 수월했다. 

arr[i] 에서 arr[i-1] 이웃 값 중 max를 취하는 방식으로 업데이트 한다.

배열의 양 끝에 위치하는 경우는 예외처리 해주고, 나머지는 arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]) .

현재 값이 i번째줄, j번째 숫자라면, i-1 번째 줄의 j-1 과 j 번째를 비교하게 된다.