DP7 [백준/C++] #11057 오르막 수 (DP) 문제https://www.acmicpc.net/problem/11057 풀이1. 팩토리얼 사용해서 integerOverflow 발생한 코드: 팩토리얼을 계산하는 과정에서 숫자가 매우 커지기 때문에 long long으로도 수를 감당할 수 없게 되어 integerOverflow 발생 사용할 수의 개수만큼 0~9중에 고르기 & 마지막 자릿수 제외한 자릿수 중에 어디"까지" 특정 수가 나올지 고르기이렇게 두 로직을 combination으로 계산할 수 있다. 예를 들면, 수의 길이가 4라고 하자. 길이가 4인 수는 숫자 4개 혹은 3개 혹은 2개 혹은 1개로 오르막 수를 구성할 수 있다. 숫자 4개를 이용하는 수를 만들기 위해서는 0~9 수들 중 중복되지 않는 수 4개를 고르고(10 C 4), 마지막 자리를 제.. 2024. 11. 11. [백준/C++] #1904 01타일 (DP) 문제https://www.acmicpc.net/problem/1904 풀이 (총 소요 21m)1. 시간초과 나는 재귀 풀이: make 함수가 모든 가능한 타일 배열을 만드는 모든 경우를 확인하면서 진행. 즉, 재귀 방식으로 호출되는 모든 부분 문제를 반복적으로 해결하게 되면서 계산량이 매우 커지고 시간 초과가 발생하게 됨.#include#include#define endl "\n"using namespace std;int leng;int num = 0;void make(int length) { if (length == leng) { num++; num %= 15746; return; } else { if (length + 2 > leng;.. 2024. 11. 11. [백준/C++] #1005 ACM Craft (DP) 문제https://www.acmicpc.net/problem/1005구상문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!! 구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이.. 2024. 8. 9. [백준/C++] #1509 팰린드롬 분할 (DP) 문제https://www.acmicpc.net/problem/1509 구상확실히 골드 1이 느껴지는 문제였다. 그래도 차근차근 접근하니 옳은 풀이까지 도달할 수 있었다. 역시나 DP말고 특별한 접근 방식이 떠오르지 않아서 DP로 접근을 했다. 작은 길이의 팰린드롬 분할의 개수의 최솟값을 통해 더 큰(긴) 팰린드롬 분할의 개수의 최솟값을 구할 수 있었다. 그래서 처음에는 흔한 다른 DP문제들과 유사하게 접근을 했다. 흔한 DP 문제들은 DP배열의 특정 값이 답이 되는데, 그래서 나도 DP[i][j]가 str[i]~str[j]문자열에서 팰린드롬 분할의 개수의 최솟값이라고 잡고 문제를 접근했다. 그런데, 특정 크기의 문자열이 팰린드롬인지 확인하는 로직이 필요했다. 팰린드롬 여부를 어떻게 확인할까? 생각하다가.. 2024. 7. 24. 이전 1 2 다음