※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25633번 문제인 도미노 넘어뜨리기이다.
문제는 아래 링크를 확인하자.

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

 

25633번: 도미노 넘어뜨리기

$N$개의 도미노가 일렬로 세워져 있다. 도미노에는 무게가 존재하는데, $i$번째 도미노의 무게는 $a_i$이다. 단현이는 $N$개의 도미노 중 일부 도미노를 제거할 수 있다. 만약 남은 도미노에서 $i$번

www.acmicpc.net

i-1번째 도미노가 쓰러졌을 때까지의 기록을 이용하면, i번째 도미노가 쓰러질 때 총 k(1이상 i이하)개 쓰러진 것이 되는 각 상황에 대한 정보를 갱신해나가며 문제를 해결할 수 있다. 예를 들어, 5번째 도미노가 쓰러지는 상황을 생각하면, "도미노가 5개 쓰러질 경우(가능하다면)의 도미노의 무게의 합의 최댓값", "도미노가 4개 쓰러질 경우(가능하다면)의 도미노의 무게의 합의 최댓값", ..., "도미노가 1개 쓰러질 경우의 도미노의 무게의 합의 최댓값"을 갱신해나가는 것으로 문제를 해결할 수 있다.

 

별해로, 각 i번째 도미노를 처음 쓰러뜨리는 도미노로 생각해 greedy한 방식으로 도미노들을 쓰러뜨려보는 시뮬레이션을 전부 돌려 해결할 수도 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[1001];
int dp[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	for (int i = 1; i <= N; i++) {
		for (int j = i; j > 0; j--) {
			if (dp[j - 1] == 0) continue;
			if (dp[j - 1] >= arr[i]) dp[j] = max(dp[j], dp[j - 1] + arr[i]);
		}
		dp[1] = max(dp[1], arr[i]);
	}

	for (int i = N; i > 0; i--) {
		if (dp[i]) {
			cout << i;
			break;
		}
	}
}
728x90

+ Recent posts