※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 25633번 문제인 도미노 넘어뜨리기이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/25633
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
'BOJ' 카테고리의 다른 글
[BOJ 25869 // C++] Window on the Wall (0) | 2022.11.06 |
---|---|
[BOJ 25634 // C++] 전구 상태 뒤집기 (0) | 2022.11.06 |
[BOJ 25829 // C++] Presidential Election (0) | 2022.11.05 |
[BOJ 25932 // C++] Find the Twins (0) | 2022.11.05 |
[BOJ 25830 // C++] Microwave Mishap (0) | 2022.11.05 |