[동적계획법/DP] 백준 1660 캡틴 이다솜 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1660번: 캡틴 이다솜

 

 

 

2. 문제 풀이

 대포알을 반드시 사면체 모양으로 쌓아둘 때, 주어진 대포알로 만들 수 있는 최소의 '사면체'를 구하는 문제입니다.

 

2022.05.09 - [Algorithm] - [동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python)

[동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python)

 대표적인 DP문제인 '배낭 문제'와 유사합니다. 물건의 무게가 '사면체에 필요한 대포알'이고, 최대한 적은 물건을 넣는 DP문제입니다. 사면체에 필요한 대포알은 [1, 4, 10, 20 ... ] 순이며 주어진 대포알(N)보다 클 때까지 계산해야 합니다.

 

 

 

3. 코드

# 입력
N = int(input())

# 사면체에 필요한 포탄 수 계산
item = [1]  # 3, 6, 10, 15씩 늘어남
plus = 3  # 포탄이 늘어나는 개수
for i in range(300001):
    # 포탄 개수가 부족해지면 종료
    if item[i] >= N:
        break
    item.append(item[i] + plus)
    plus += (3+i)

 사면체를 만드는 데에 필요한 대포알의 개수를 무작정 구현하면 위와 같습니다.

 

1 - 4(+3) - 10(+6) - 20(+10) - 35(+15)

 사면체가 커질수록 필요한 대포알의 개수는 3, 6, 10, 15와 같이 등차 1씩 커지는 수열이므로, 등차를 1씩 늘리며 더해주면 구할 수 있습니다.

 

 

 

# 사면체 개수 구하기 DP
cache = [3000000] * (N+1)
for i in range(1, N+1):
    for size in item:
        # 사면체에 필요한 포탄 수보다 적은 경우 break
        if size > i:
            break

        # 사면체에 필요한 포탄 수와 동일하면 1개
        elif size == i:
            cache[i] = 1
            break

        # 사면체에 필요한 포탄 수보다 많은 경우
        else:
            cache[i] = min(cache[i], 1 + cache[i-size])
print(cache[N])

 사면체를 이루는 데 필요한 개수를 구했으니, 이제 사면체를 넣고 빼면서 최소 개수를 찾습니다.