문제링크 : https://www.acmicpc.net/problem/1937
문제 접근
- 각 노드에서 DFS로 모든 경우의 수 사용할 경우
- 모든 노드 : O(N^2)
- 각 노드에서 DFS할경우, O(V+E) : O(N^2 + 4 * N^2) : O(5*N^2)
- O(N^2 * 5N^2) = O(5N^4) = 5*625 * e8 > 시간초과
- DP를 사용, 각 노드 : 판다가 최대한 살수 있는 일수
- 각 노드에서 값 구하기 위해 DFS 사용
- 4방향에서 현재보다 값 작을경우, DP 값있으면 반환하고, 없으면 다시 DFS
- O(V+E) : O(5*N^2)
시간복잡도 계산
- DP 사용하면, 가장 높은 값을 갖는곳으로부터 DFS 한것과 같은 효과
- O(V+E) = O(N^2 + 4N^2) = O(5*N^2)
인트 계산
- 대나무 양 : 1e6보다 작음 > INT 가능
- DP 값 : 25e4보다 작음 > DP 가능
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <iostream> using namespace std; int map[510][510]; int dp[510][510]; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; int get_dp(int y, int x) { if(dp[y][x] != 0) return dp[y][x]; int rs=0; for(int k=0; k<4; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if(map[y][x] < map[ny][nx]) rs = max(rs, get_dp(ny, nx)); } return dp[y][x] = rs+1; } int main() { int N; cin >> N; fill(&dp[0][0], &dp[509][510], 0); for(int j=0; j<N; j++) { for(int i=0; i<N; i++) { cin >> map[j][i]; } } int rs=0; for(int j=0; j<N; j++) { for(int i=0; i<N; i++) { rs = max(rs, get_dp(j,i)); } } cout << rs << '\n'; return 0; } | cs |
문제유형
- DP - DFS
- DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
- 특히 2차원에서 상하좌우를 모두 고려해줘야할 때
비슷한 문제
'알고리즘 > 백준' 카테고리의 다른 글
백준 2565 전깃줄 쉬운 풀이(C++/CPP) (0) | 2021.02.15 |
---|---|
백준 1946 신입 사원 (0) | 2021.02.15 |
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
백준 11657 타임머신 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |