[백준] 11066: 파일 합치기(assert 사용으로 디버깅 🐛)

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

11066번: 파일 합치기

이 문제를 처음에 보면 앞뒤로 연속되게 합쳐질 수 있어서 일반적인 다이나믹 프로그래밍이 떠오르지 않을 수 있다.

그래도 중복 문제가 발생하기 때문에 다이나믹 프로그래밍으로 풀고 싶다는 욕구가 든다.

 

그렇다면 중복 문제는 어떻게 해결해야하는가?

 

어떠한 구간의 합이 궁금하다면 해당 구간을 임의로 두 부분으로 나누어서 왼쪽 부분과 오른쪽 부분을 합친 비용의 최솟값이 될 것이다.

두 부분을 나누는 부분은 당연하게도 해당 구간의 내부 값이면 아무거나 가능하다.

 

$dp[i][j] = max_{k = i}^{k < j} dp[i][k] + dp[k + 1][j]$

 

여기서 조금 더 생각해보면 앞서 푼 https://dleunji.tistory.com/135 와 상당히 유사하다는 점이 떠오른다.

135번 문제처럼 반드시 두 부분으로 분할하여 풀어야 한다는 점, 2차원 배열로 특정 출발점부터 도착점까지의 합을 구하는 점이 동일하다.

 

하지만 차이점은 여기서는 배열을 두 개로 써야한다.

비용 전체를 표현하는 sum, 오직 파일의 누적합만을 표현하는 dp

 

그런데 이렇게 핵심을 풀고도 자꾸 틀려서 힘들었는데 해결해보니 초기화의 문제였다.

sum 배열을 선언만 하면 자동으로 초기화될 것이라고 착각하였다.

사실 중간에 쓰레기값들이 있는데 테스트케이스에서는 드러나지 않았었다.

 

이것도 까먹고 왜 0으로 초기화하면 오류가 나고, -1로 초기화하면 잘 돌아갈까라고 의문을 가졌다.

당연히 0일 때는 선언한 배열 그대로 사용하고, -1일 때는 수동으로 초기화해줬어야 했기 때문이다..

이런 것도 까먹고 assert로 입력되는 파일크기의 데이터에 음수의 값이 있는지 확인하고 난리를 쳤다..ㅎㅎ.ㅎ.ㅎ.....

https://www.acmicpc.net/board/view/91529#post

글 읽기 - 문제의 조건과 채점 케이스가 상충되는 것 같습니다..

처음에는 데이터 이슈인 줄 알았어서 질문도 남겼었다..;;

하지만 알고보니 0일 때는 초기화 자체를 놓쳤던 것이다...

하도 최근에 다양한 언어를 다루면서 자동으로 초기화되는 것으로 착각하고 말아버린 나..

C 기반은 그렇게 호락호락하지 않다구!!

 

ㅠㅠ

 

그래도 덕분에 백준에서 assert 사용방법을 터득할 수 있어서 좋은 기회였다!