Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- c++
- 카카오인턴
- Union-find
- 중반부
- 유니온파인드
- 서버개발캠프
- 소감
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 1편
- 카카오
- 백준
- BaekJoon
- LIS #Algorithm #요소추적
- Smilegate
- Algorithm
- 코테
- 투포인터
- 보석쇼핑
- 스마일게이트
- BFS
- 코딩테스트
- 알고리즘
- 삼성 #코테 #2020상반기 #c++
- 식단
Archives
- Today
- Total
짱아의 개발 기록장
백준 17130번. 토끼가 정보섬에 올라온 이유(c++) / DP 본문
반응형
DP가 아닌, BFS로도 풀 수 있는 문제이다.
행과 열의 값이 최대 1000이기 때문에 무리 없이 풀 수 있지만, DP로 풀기에 최적화된 문제라고 생각한다.
토끼가 →, ↘, ↗ 방향으로만 이동할 수 있기 때문에 현재 위치에서 그 전의 지점에서 올 수 있는 경로를 파악하여 dp값을 계속적으로 3지점의 최대값으로 갱신해주는 식으로 구현했다.
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | // 토끼가 정보섬에 올라온 이유 #include <cstring> #include <iostream> using namespace std; int n, m, startX, startY; string s; int dp[1001][1001] = {0, }; char map[1001][1001]; int ans = 0; bool check = false; void rabbitMove() { for(int j=startY; j<m; j++){ for(int i=0; i<n; i++){ if(map[i][j]=='#') continue; if(i-1>=0 && j-1>=0 && dp[i-1][j-1]!=-1){ dp[i][j] = max(dp[i][j], dp[i-1][j-1]); } if(j-1>=0 && dp[i][j-1]!=-1){ dp[i][j] = max(dp[i][j], dp[i][j-1]); } if(i+1<n && j-1>=0 && dp[i+1][j-1]!=-1){ dp[i][j] = max(dp[i][j], dp[i+1][j-1]); } if(map[i][j]=='C' && dp[i][j]!=-1){ dp[i][j]++; } if(map[i][j]=='O' && dp[i][j]!=-1){ check = true; ans = max(ans, dp[i][j]); } } } } int main() { memset(dp, -1, sizeof(dp)); cin>>n>>m; for(int i=0; i<n; i++){ cin>>s; for(int j=0; j<s.size(); j++){ map[i][j] = s[j]; if(map[i][j]=='R'){ startX = i; startY = j; dp[i][j] = 0; // 경로의 시작! } } } rabbitMove(); if(check){ cout<<ans<<"\n"; }else{ cout<<"-1"<<"\n"; } return 0; } | cs |
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
백준 2533번. 사회망 서비스(SNS) (c++) / Tree+DFS+DP 🌟문제 굿!🌟 (0) | 2021.04.19 |
---|---|
백준 14916번. 거스름돈(c++) / Greedy (0) | 2021.04.17 |
백준 2660번. 회장뽑기(c++) / BFS (0) | 2021.04.13 |
백준 3079번. 입국심사(c++) / 이분탐색 (1) | 2021.04.13 |
백준 1103번. 게임(c++) / DP+DFS (0) | 2021.04.13 |