백준 1660번 캡틴 이다솜

문제 링크 : https://www.acmicpc.net/problem/1660

문제풀이

사용한 알고리즘 : DP

(1) 코드 6~8

 'triangle[k] = 사이즈 k의 사면체 만들 때 필요한 대포알 수'라고 설정하였습니다. 

 N이 최대 3*10^5 으로 주어지므로, 배열 크기는 넉넉히 200 정도로 했습니다. 

(2) 코드 31~34

 과정(1)에서 만들어 놓은 사면체를 만들 때 필요한 대포알 개수를 구해줍니다.

 i번째에서 추가되는 대포알 수는 1+2+...+i = i*(i+1)/2 인 것을 생각해줍니다.

(3) 코드 8~10

 'dp[x] : x개의 대포알로 만드는 최소 사면체 수' 라고 설정하였습니다.

(4) 코드 12~27

 임의의 수 x가 주어졌을 때, x개의 대포알로 만드는 최소 사면체 수를 구하는 함수입니다.

 주어진 x크기로 만들 수 있는 k사이즈의 사면체를 각각 만들어 보면서,

 구하고자 하는 x개의 대포알로 만드는 최소 사면체 수를 구하고, 이를 dp로 저장합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 200;
	int N;
	// triangle[k] : 사이즈 k 인 사면체 만들 때 필요한 대포알 수
	// MAX=200 : 200개 정도 잡아놓으면 3*10^5 보다 한참 크다
	int triangle[MAX];
	// dp[x] : x 개의 대포알로 만드는 최소 사면체 개수
	int dp[300005];
	int path(int x) {
	if (x == 0) return 0;
	int& ret = dp[x];
	if (ret != -1) return ret;
	ret = 1987654321; // 적당히 큰 수
	for (int i = 1; i < MAX; ++i) { // 사이즈 i인 사면체 각각 만들어보기
	if (triangle[i] > x) break;
	ret = min(ret, 1 + path(x - triangle[i]));
	}
	return ret;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 1; i < MAX; ++i) {
	int curr = i * (i + 1) / 2; // 현재 필요한거
	triangle[i] = triangle[i - 1] + curr;
	}
	cin >> N;
	memset(dp, -1, sizeof(dp));
	cout << path(N) << '\n';
	return 0;
	}

view raw BOJ 1660.cpp hosted with ❤ by GitHub