[Python] 1106번 호텔

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

 

#1.입력
C,N=map(int,input().split()) #C:people,N:city
cost,people=[0],[0]
for _ in range(N):
    c,p=map(int,input().split())
    cost.append(c)
    people.append(p)
#2.자료형 정의
dp=[float('inf') for _ in range(C+1)]
dp[0]=0  # 0명 모집 비용은 0
#3.동작함수
for n in range(1,N+1):
    for c in range(1,C+1):
        case1=min(dp[c],((c+people[n]-1)//people[n])*cost[n])
        case2 = float('inf')
        if c-people[n]>=0:
            case2=dp[c-people[n]]+cost[n]
        dp[c]=min(case1,case2)
#4.출력
print(dp[C])

 

코드가 맞기까지 오래 걸렸다ㅜㅜ

틀렸던 이유)

C명에 칼 같이 맞추는게 아닌, C명 이상인 경우로 고려해야함.

c-people[n] 값이 0보다 작을 경우 고려를 못함.

#1.입력
C,N=map(int,input().split()) #C:people,N:city
cost,people=[0],[0]
for _ in range(N):
    c,p=map(int,input().split())
    cost.append(c)
    people.append(p)
#2.자료형 정의
dp=[float('inf') for _ in range(C+1)]
#3.동작함수
for n in range(1,N+1):
    for c in range(1,C+1):
        case1=dp[c] #현재값
        m=c//people[n]
        if c%people[n]==0: #나누어 떨어진다면
            case3=m*cost[n]
        else: case3=(m+1)*cost[n]
        case1=min(case1,case3)

        if c-people[n]<0:
            case2=float('inf')
        else: case2=dp[c-people[n]]+cost[n]
        dp[c]=min(case1,case2)
#4.출력
print(dp[C])

이건 처음 맞았던 코드고 이 코드를 정리한게 위에 코드다.