[백준] 2630, 2839 - Python3

2839. 설탕 배달

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

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())
nums = [-1]*(N+1)

if N == 3:
    print(1)
elif N == 4:
    print(-1)
else:
    nums[3] = 1
    nums[5] = 1

    for i in range(6, N+1):
        if nums[i-5] != -1:
            nums[i] = nums[5] + nums[i-5]
        elif nums[i-3] != -1:
            nums[i] = nums[3] + nums[i-3]
    print(nums[N])

nums 리스트를 만들어서 처음 3, 5 만 1 로 초기화

3, 4 일 경우는 예외 처리해주고
5 이상일 경우는 반복문 돌려서 dp 이용

5 를 뺀 값이 3 을 뺀 값 보단 작은 값이 될 것이므로
nums[i-5] 부터 확인하고 nums[i-3] 확인
둘 다 -1 이면 그대로 통과

N 번째 값 print

크게 어려운 문제가 아녔는데
N 이 3, 4, 5 일 때의 예외처리를 제대로 안해줘서 엄청 오래 걸렸다...ㅎ
IndexError => 항상 범위 체크를 잘 할 것!!!!

---

2630. 색종이 만들기

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

내 풀이 - 성공

from sys import stdin
import collections

N = int(stdin.readline())

papers = []
for _ in range(N):
    p = list(map(int, stdin.readline().split()))
    papers.append(p)

white = 0
blue = 0

def func(si, sj, ei, ej, n):
    global white, blue

    value = papers[si][sj]
    cut = 0
    for i in range(si, ei):
        for j in range(sj, ej):
            if value != papers[i][j]:
                cut = 1
                break
        if cut:
            break
    
    if cut:
        func(si, sj, si+n//2, sj+n//2, n//2)  # 1
        func(si, sj+n//2, si+n//2, sj+n, n//2)  # 2
        func(si+n//2, sj, si+n, sj+n//2, n//2)  # 3
        func(si+n//2, sj+n//2, si+n, sj+n, n//2)  # 4
    else:
        if value == 0:
            white += 1
        else:
            blue += 1

func(0, 0, N, N, N)

print(white)
print(blue)

func 함수)
현재 구역이 모두 같은 값으로 이뤄져있는지 판단
모두 같은 값이면 white / blue update

다른 값이 하나라도 있으면 break 후 4 등분
=> 전체 길이의 절반 (n//2) 을 (si, sj) 를 기준으로 더함

분할정복을 이용했다