이 문제를 보고 DP 를 사용해야 되겠다고 생각하였다.
DP 문제를 많이 다루지 못해서 이 문제는 충분히 생각한 뒤
다른 사람의 풀이를 참조 하여 코드를 해석하고 왜 이런 코드를 썼는지 이해하였다.
다음 문제를 풀땐 내가 직접 풀어보자 ...
우선 코드를 해석하였을 때
체크 해야 할것들이 여러가지가 있는데
첫 번째 도현이의 위치
두 번째 과거 허들 높이
세 번째 현재 허들 높이
네 번째 허들의 높이가 2이상인 경우가 있는가 ?
이 4개를 고려하여 동적 프로그래밍을 해야한다.
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
long long dp[1001][3][3][2];
long long mod = 1000000007;
int N;
long long solve(int now, int state, bool flag, int laststate) {
long long &ref = dp[now][state][laststate][flag];//현재위치 , 현재 높이 , 과거 높이 , flag(높이 2이상인가?)
if (now == N - 1) {//현재위치가 끝까지 갔을 때
if (flag)
return ref = 1;
else
return ref;
}
if (ref != 0)
return ref;
if (state == 0) {
ref += solve(now + 1, 0, flag, state) % mod;
ref += solve(now + 1, 1, flag, state) % mod;
ref += solve(now + 1, 2, true, state) % mod;
}
else if (state == 1) {
if (laststate == 0) {
ref += solve(now + 1, 0, flag, state) % mod;
ref += solve(now + 1, 1, flag, state) % mod;
ref += solve(now + 1, 2, true, state) % mod;
}
else {//허들 2개이상을 한번에 넘을수 없다.
ref += solve(now + 1, 0, flag, state) % mod;
}
}
else if(state == 2){
if (laststate == 0) {
ref += solve(now + 1, 0, flag, state) % mod;
ref += solve(now + 1, 1, flag, state) % mod;
}
else {//허들 2개이상을 한번에 넘을수 없다.
ref += solve(now + 1, 0, flag, state) % mod;
}
}
return ref = ref % mod;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
cin >> N;
cout << solve(0, 0, false, 0) << "\n";
}
코드 출처 : countrysides.tistory.com/51
이 문제를 보면서 그동안 풀어왔던 문제들보다 한단계 어려워진 것 같다.
고등학교 선생님께서 자주하셨던 말이 있다...
갈길이 멀다.
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 7662번 문제풀이 (0) | 2021.02.22 |
---|---|
[C++] 백준 20546번 문제풀이 (0) | 2021.02.21 |
[C++] 백준 7576번 문제풀이 (0) | 2021.02.19 |
[C++] 백준 2630 문제풀이 (0) | 2021.02.16 |
[C++] 백준 2606 문제풀이 (0) | 2021.02.16 |