백준님께서 dp강의에서 설명하신 문제들을 정리하면서 이해해 보려고 한다.
dp잘하고 싶다.
BOJ 5626 제단
문제 설명
N열짜리 제단을 만드려고 하는데, 제단의 각 높이는 모두 정수이고, 가장 처음에 모든 열의 높이는 0이다.
제단을 만드는 과정은 다음과 같다.
1. 같은 높이를 가지는 연속하는 열을 선택한다.
2. 그 다음 선택한 첫 열과 마지막 열을 제외한 모든 열의 높이를 1만큼 올린다.
이렇게 만든 제단의 일부 열을 도둑 맞아 일부 열의 높이 정보만 남아있다. 이 때, 남아 있는 열들의 정보를 가지고 가능한 원래 제단의 경우의 수를 구하는 문제이다.
입력
첫째 줄에 제단의 열의 수 N이 주어진다.(1 <= N <= 10000)
다음 줄에는 공백으로 구분된 N개의 정수 hi가 주어진다.( -1<=h1<=10000) hi는 i번 열의 높이를 나타내며, -1인 경우에는 도둑이 그 열을 훔쳐간 상태를 나타낸다.
출력
첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제 입력
6
-1 -1 -1 2 -1 -1
예제 출력
3
예제 설명 : -1로 되어있는 열은 도둑이 훔쳐간 열이므로 정보를 알 수 없다. 지금 4번째 열에 높이가 2인 제단이 있다는 것만 알 수 있다.
4번째 열에 높이가 2인 제단이 있을 수 있는 경우의 수는 총 3가지이다.
(0, 0, 1, 2, 1, 0) , (0, 1, 1, 2, 1, 0) , (0, 1, 2, 2, 1, 0)
풀이
제단은 아래와 같은 세 가지 조건을 만족하는 히스토그램이라고 생각할 수 있다.
1. 첫 열과 마지막 열의 높이는 0이다.
- 같은 높이를 가지는 연속한 열을 선택한 후, 첫 열과 마지막 열을 제외한 열의 높이를 1 올리므로, 즉 첫 열과 마지막 열을 제외하고 제단을 쌓기 때문에 어떻게 쌓든 첫 열과 마지막 열의 높이는 0일 수 밖에 없다.
2. 인접한 열의 차이는 최대1이다.
- 같은 높이를 가지는 연속한 열을 선택해서 첫 열과 마지막 열을 제외한 열의 높이를 1 올리기 때문에, 인접한 열의 차이는 0이거나 1일 수 밖에 없다.
3. 음수 높이를 갖는 열은 없다.
- 가장 처음에 모든 열의 높이는 0이고, 열의 높이를 올리기만 하기 때문에 음수가 나올 수 없다.
풀이
식 : d[k][h]= k번째 열의 높이가 h일 때, k번째 열까지의 가능한 제단의 경우의 수
d[k][h]=d[k-1][h] + d[k-1][h+1] + d[k-1][h-1] (-1이거나, 주어진 높이와 같은 경우를 조건으로 해야함)
- 이 문제는 백준님의 풀이와 코드를 보고 풀기 시작했는데, 틀려서 결국 백준님의 코드와 대조하고 테스트케이스를 대조해서 AC를 받았다. 틀린 이유는 3가지 였는데,
첫 번째는 메모리 초과였다. 점화식을 보면 알겠지만 값을 구하기 위해서 결국 직전 값만 필요하기 때문에 이건 sliding window기법으로 해결할 수 있다.
나머지 두 개의 이유는 모두 sliding window로 풀어서 생길 수 있는 문제이고, 주의해야하는 문제인데, 코드에 주석으로 달아놨는데 여기에 그대로 복사 붙여넣기 해놔야겠다.
//이렇게 sliding window기법을 쓸 때는, 구하고자 하는 값을 n으로 놓고
//결국 n에 관한 값만 나오게 되므로, 0과 1같은 작은 수가 구하고자 하는
//값이면 따로 예외처리를 해줘야 한다.
-> n이 2이상의 수만 들어오리라 생각하고 for문을 2부터 돌린다. 근데 배열은 update
되므로 0과 1에 해당하는 값은 다른 값이 들어가리라... 생각했지만 그게 아니다 아예 for문에 들어가지도 않을텐데.. 이 문제에선 n이 1일때, 입력받은 높이가 중요하다. 입력받은 높이가 0이나 -1이면 답이 1이지만, 그 외에는 0인데, 원래 코드에서는 d[1][0]=1로 초기화를 해놔서 무조건 1이 나오게 됐고, WA. 그래서 따로 예외처리를 해서 AC를 받았다.
//이렇게 중간 중간에 0으로 초기화하지 않으면
//다음 단계에서 값이 안들어가도 0이 아닌 다른 값을 갖게 될 수 있어서
//그 다음 단계에서 0이 아닌 잘못된 값이 이용될 수 있을 것 같다.
-> 내가 여태 for문으로 dp를 구현한 적이 별로 없어서(해도 쉬운 문제만), 오늘 처음 본 경우인데, 이 문제에서는 직전 값을 이용해서 원하는 값을 구하면 직전 값을 0으로 초기화해야한다. 내가 이전까지 알기로는 어차피 직전 값이 있던 메모리에 새로운 구하고자 하는 값으로 덮어 씌워지기 때문에 굳이 초기화 할 필요 없는 것인데...
이 문제는 점화식 특성상 모든 값이 업데이트가 되는 것이 아니고 업데이트 되지 않는 값도 있을 수 있고, 업데이트 되지 않는 경우 그 경우가 없는 것이며 그 메모리에는 0이 들어가야한다. 하지만 중간에 초기화를 안해주면 0이 아닌 직전값이 들어가있어서 다음 값을 구하는데 문제가 되는 것 같다.
비록 내 힘으로 풀지는 않았지만 많이 배웠고, 정말 좋은 문제이다.
추가) 다시 풀고 예전 코드롤 봤는데, 난 중간 중간에 모두 0으로 초기화했었다. 하지만 그럴 필요까지는 없다. 값이 업데이트되지 않는 경우만 0으로 초기화하면 된다. 값이 업데이트 되지 않는 경우는 d[k][h]에서 h값이 입력으로 주어진 높이와 같지 않거나, -1이 아닌 경우이다. 이 경우들은 성립되지 않는 경우이므로 0으로 초기화하면 된다. 그리고 예전 코드에서는 무조건 += 방식을 취하고 있어서 모두 0으로 초기화할 필요가 있었던 것 같다. d[k-1][h]+ d[k-1][h+1]은 대입(=)을 해주고, d[k-1][h-1]인 경우만 (h가 0이 아닐때) +=연산을 해주면 된다.
그리고 제단의 높이의 최대값은 n/2를 넘을 수 없으므로 배열의 크기나, for문을 n/2 크기로 잡는 것이 메모리나 시간을 단축할 수 있다.
마지막으로 n이 1인 경우 높이가 0과 -1이 아닌 경우에는 경우의 수 0을 출력하는 부분을 따로 만들었었는데, 그럴게 아니라 d[1][0]= h[1]<=0 ? 1 : 0 ; 이런 식으로 하는 게 더 나아보인다. 이렇게 하면 n이 1보다 크고, h[1]이 0보다 큰 값이 들어온 잘못된 경우에도 경우의 수 0을 출력할 것이기 때문이다.
주의할 점 추가+) n/2까지 돌리고, 배열을 n/2까지 하는 건 좋은데, 주의해야 한다. 배열을
d[2][5001]로 잡고, n/2까지 돌릴 경우, 실제 배열은 d[ ][5000]까지 존재하는데,
d[k-1][h+1]부분에서 d[ ][5001]까지 참조하게 된다. 즉, 없는 부분을 참조하게 되어 계속 틀렸다. 배열을 크게 좀 더 여유있게 해줘야 한다.
댓글 없음:
댓글 쓰기