DP5 [백준/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. [백준/C++] #11049 행렬 곱셈 순서 (DP) 문제https://www.acmicpc.net/problem/11049 구상행렬 곱셈 연산의 수의 최솟값을 구하는 문제였다. 해당 문제가 11066번(https://persi0815.tistory.com/47)과 같이 작은 부분을 통해 큰 부분의 값을 알아낼 수 있었다. 처음에 착각했던게, a b c d라는 배열이 있으면, abc * d와 a* bcd의 연산만 가능하다고 생각했었다. 사실 ab*cd도 되는데.. 그래서 해당 부분 수정해서 로직을 짰더니 성공 !!알고리즘이전에 구한 값으로 다음 값을 구하니 dp 유형이다. 풀이 + 코드dp[i][j]는 행렬 i부터 행렬 j까지의 최소 행렬 곱셈 연산 수이다. 최악의 연산수도 범위가 2^31-1보다 작다고 해서 int를 사용했다. #include#incl.. 2024. 7. 23. [백준/C++] #11066 파일 합치기 (DP) 문제https://www.acmicpc.net/problem/11066 구상문제 풀이가 생각이 안나면 나는 일단 DP로 접근을 해본다. 이 문제도 그러했는데, DP로 접근해보니 풀이가 보였다. 이전 합치는 비용을 이용해서 다음 합치는 비용을 구했다. DP를 사용할 때는 획일화된 기준이 중요해서 첫 기준을 파일 길이로 잡고 다음 기준을 파일 시작 위치로 정했다. 그랬더니 파일 끝 위치는 저절로 설정할 수 있었고, 다음 기준을 분할 위치로 잡았다. 그렇게 마지막 식을 보면 알 수 있듯이 이전 값들을 이용해서 보다 큰 다음 비용을 구할 수 있었다. 알고리즘이전 합치는 비용 이용해서 다음 합치는 비용을 구하니까 DP를 이용했다. 풀이 + 코드dp[i][j]: 파일 i부터 j까지 합치는 데 필요한 최소 비용. .. 2024. 7. 23. 이전 1 2 다음
