[파이썬] 백준 1636 : 한번 열면 멈출 수 없어 (골드4)

[파이썬] 백준 1636 : 한번 열면 멈출 수 없어 (골드4)

1636번: 한번 열면 멈출 수 없어

---

문제

---

풀이

0. 방향성 생각

• DP. 입력이 10만이라 10**6 *201 사이즈로 만드는건 힘들다.
• 각 프링글스 범위에 맞는 사이즈로 넣어준다.

1. 입력

n = int(input())
inf = 1e9
info,dp,trace = [],[],[]
for i in range(n):
    a,b = map(int,input().split())
    info.append((a,b))
    if i == 0:
        dp.append([inf]*(b-a+1))
        trace.append([-1]*(b-a+1))
    dp.append([inf]*(b-a+1))
    trace.append([-1]*(b-a+1))

• 프링글스를 n번 먹으면 총 n+1개 상태가 나옴
• 최소값 찾기 + 각 상태까지 필요하므로 dp,trace 두개 설정
• dp, trace에 각 범위에 맞게 b-a+1로 넣는다

2. 함수 정의

s1,e1 = info[0]
dp[0] = [0]*(e1-s1+1)
trace[0] = list(range(s1,e1+1))
for idx,rg in enumerate(info):
    s2,e2 = rg
    for x in range(s1,e1+1):
        for nx in range(s2,e2+1):
            diff = abs(x-nx)
            if dp[idx][x-s1] + diff < dp[idx+1][nx-s2]:
                dp[idx+1][nx-s2] = dp[idx][x-s1] + diff
                trace[idx+1][nx-s2] = x
    s1,e1 = rg

• idx번째 과자 먹을 때 스트레스를 x에서 nx로 조절할 때, dp 테이블 값이 최소값으로 갱신되면 trace에 이전 경로 x를 추가함
• 처음 범위는 s1,e1에서 s2,e2로 매핑
• 한 과자를 다 먹고 매핑이 끝나면 s2,e2를 다시 s1,e1에 놓고 다음 루프에서 매핑시킴

3. 출력

answer = []
midx,mval = 201,inf
for idx,val in enumerate(dp[-1]):
    if val < mval:
        midx,mval = idx,val
answer.append(info[-1][0]+midx)

for i in range(n-1):
    answer.append(trace[-i-1][answer[-1]-info[-i-1][0]])

print(min(dp[-1]))
for a in answer[::-1]:
    print(a,sep = '\n')

• 마지막 DP에서 최소값을 찾고 역추적
• answer[-1]-info[i-1][0] 이부분은 DP가 201 사이즈로 만들어진게 아니라서 인덱스 매핑

 

---

전체코드

n = int(input())
inf = 1e9
info,dp,trace = [],[],[]
for i in range(n):
    a,b = map(int,input().split())
    info.append((a,b))
    if i == 0:
        dp.append([inf]*(b-a+1))
        trace.append([-1]*(b-a+1))
    dp.append([inf]*(b-a+1))
    trace.append([-1]*(b-a+1))

s1,e1 = info[0]
dp[0] = [0]*(e1-s1+1)
trace[0] = list(range(s1,e1+1))
for idx,rg in enumerate(info):
    s2,e2 = rg
    for x in range(s1,e1+1):
        for nx in range(s2,e2+1):
            diff = abs(x-nx)
            if dp[idx][x-s1] + diff < dp[idx+1][nx-s2]:
                dp[idx+1][nx-s2] = dp[idx][x-s1] + diff
                trace[idx+1][nx-s2] = x
    s1,e1 = rg

answer = []
midx,mval = 201,inf
for idx,val in enumerate(dp[-1]):
    if val < mval:
        midx,mval = idx,val
answer.append(info[-1][0]+midx)

for i in range(n-1):
    answer.append(trace[-i-1][answer[-1]-info[-i-1][0]])

print(min(dp[-1]))
for a in answer[::-1]:
    print(a,sep = '\n')

 

코멘트

동작 시간도 그렇고 이렇게 풀면 안될거같은데 일단 맞았음.