#1660: 캡틴 이다솜

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

1660번: 캡틴 이다솜

Introduction

보자마자 평범한 배낭1이 떠올랐다.

---

Body

일단 그리디로는 풀 수 없다. 스터디에 어떤 분이 그리디를 특이하게 짜셨던데 결국 실패했다. 따라서 DP로 모든 경우를 확인해줘야 한다. 그리디이냐 DP이냐의 판단은 사실 너무 어렵고 문제를 많이 풀어볼 수밖에 없는 것 같다.

https://www.acmicpc.net/board/view/46178

글 읽기 - 문제를 풀때 dp로 풀어야할지 그리디로 풀어야할지 어떻게 구분하나요

여기 댓글을 다신 분이 직관적으로 설명해주셨다.

---

code

const int INF = 1<<30;
int table1[1<<10];
int table2[1<<10];

DP에서 std::min()을 사용할 거라 INF를 만들어준다.

table1과 table2는 대포알의 수이다.

table1[0]=0;
for(int i=1; i<1<<10; i++) {
	table1[i] = table1[i-1]+i;
}
table2[0]=0;
for(int i=1; i<1<<10; i++) {
	table2[i] = table2[i-1] + table1[i];
}

이러면 table2에 1, 4, 10, 20,,, 의 값이 들어가게 된다.

int start;
for(int i=1; i<1<<10; i++) {
	if(n < table2[i]) {
		start = i-1;
		break;
	}
}

그 다음 주어진 수에 대해서 대포알이 몇번째 사면체까지 들어갈 수 있는지, start를 구해준다.

ex) 입력이 15면 start는 3이 들어간다. (table2[3] = 10)

이렇게 써보고 보니 이분탐색을 써도 될 것 같다. lower_bound로.

int *dp = new int[n+1];
fill(&dp[0], &dp[n+1], INF);
dp[0] = 0;
for(int i=start; i>=1; i--) {
	for(int j=table2[i]; j<=n; j++) {
		if(dp[j - table2[i]] != 0 || j == table2[i])
			dp[j] = min(dp[j], dp[j-table2[i]] + 1);
	}
}
cout<<dp[n];

그 다음엔 평범한 배낭1 때와는 좀 다르게 DP 배열을 아래에서부터 쭉 돌면서 전부 갱신해줘야 한다.

평범한 배낭 1때는 무조건 물건을 하나씩만 넣어줘야 했다. 그래서 중복되면 안되니까 위에서부터 갱신해나간 것이고, 이번 문제는 개수 제한이 없기 때문에 아래에서부터 쭉 갱신해준다.

전부 갱신하고 dp[n]을 출력하면 된다.

cf) i를 내림차순 하는 이유는 딱히 없다.

---

End

평범한 배낭 2에서 2진수를 사용해서 풀었었다. 여기서도 사용가능할 것 같다.

개수 제한이 없다는 것에서 처음에 평범한 배낭 2처럼 풀어야 하나, 생각했는데 생각해 보니 평범한 배낭 2는 개수 제한이 있었다. 그리고 전부 쓰고 보니 마지막 DP 갱신에서 if가 굳이 필요할까 생각이 들기도 한다.

그리디, DP는 역시 최대한 많이 푸는 게 좋은 것 같다. 코테가 4일 남았는데 그때까진 그리디, DP를 중심으로 풀어야겠다.