컴공 일기248
게시글 주소: https://a.orbi.kr/00068962554
백준 1937 DP / DFS 융합 문항 풀이
소감 : 본질은 DFS인데, DP의 메모이제이션 기법을 쓰지 않으면 시간 초과가 난다.
탐색 문제들은 제한 시간 + 데이터의 수를 적절히 참조하며 Time Complexity를 따져보는 것이 첫 번째다.
완전 탐색을 해야하는데, 시간이 넉넉하다면 DFS 논리 하나로 가볍게 끌고가도 되지만 데이터 수가 생각보다 많아
제한 시간 내 모든 탐색이 불가능할 것 같으면 DP 냄새를 맡을 줄 알아야 한다.
아니면 더 근본적으로 완전 탐색 상황을 의심해볼 수도 있지만…
대놓고 DFS 였으니 이 부분은 이 문제에서 큰 의미없는 접근이겠다.
#include <iostream>
#include <algorithm>
using namespace std;
// 상 -> 하 -> 좌 -> 우 순으로 DFS 탐색 순서를 정한다.
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int forest[501][501];
int DP[501][501];
int N; //find_max의 참조를 위해서 전역변수 선언
int find_max(int i, int j) {
if (DP[i][j] > 0) return DP[i][j]; // 메모이제이션
DP[i][j] = 1;
for (int k = 0; k < 4; ++k) {
int next_x = i + dx[k];
int next_y = j + dy[k];
if (0 <= next_x && next_x < N && 0 <= next_y && next_y < N) {
if (forest[i][j] < forest[next_x][next_y]) {
DP[i][j] = max(DP[i][j], find_max(next_x, next_y) + 1);
}
}
}
return DP[i][j];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int res = -1; // 결과 변수
cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> forest[i][j];
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
res = max(res, find_max(i, j));
}
}
cout << res << “\n”;
return 0;
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
국어 실모 0
이감 밖에 풀어본 적 없는데 상상이랑 이감 중 뭐가 더 나은가요? 비슷비슷한가요?
-
서울대 인문계열 입학 vs 세무사 자격증 획득 무엇을 선택할 것인가요?? 진짜 궁금하네요
-
꼬기 등장 3
나 취해써
-
아가취침 6
1교시 ㅋㅋ
-
내신 2.5 2
내신 2.5 인서울 적정권이 어디인가요??? 생기부는 평범하다는 가정하에 알려주세욥
-
맞아도 되나여 딴건 1컷 수준에 국어 백분위 98이상은 나오는데
-
메가나 19패스 보통 언제쯤 나오나요?
-
오르비는 성비가 3
어케 되나요 걍 궁금해서요
-
수리논술 어케 나오나요?? 작년에 냥대 안 써서 잘 모르겠음여... 통통이고 수학...
-
책이 안팔려 5
누군가 좀 사줘요ㅠㅠ 아예 가격을 더 낮게 불러야하나
-
3급 고졸인데 갈 수 있으면 무조건 가는 게 좋음? 대학 갈지 말지 고민임
-
경기대 영어영문학과 KGU학생부종합전형한국외국어대학교 글로벌캠퍼스 융합인재대학...
-
강제기상은 시러,,
-
한번더 치셔야하거나 지금 고2들은 수능끝나고 연락주세요
-
한약학과 3
실시간 인기 검색어 1위 이건 ㄹㅇ 처음인것 같은데요?ㅋㅋㅋ
-
문제 계속 풀고 복습하면서 체화하는 방법 밖에 없나요,,,,, 매번 볼때마다 새로운 느낌이 드네요ㅜ
-
오늘의공부 2
국어2지문 영어 5지문+실모+수업 수학 숏컷 15문제+실모 사문 실모 한지 노트 복습
-
제목이 곧 내용입니다 너무 셀프로 신상 공개하는 거 같으면 조금 넓은 영역도 좋아요...
-
친구중에 2.6으로 고대, 서강, 중앙, 경희, 시립, 건국 쓴 얘 있었는데 고대...
-
92점………. 미적분 ㅂㅅ실력 재등장 공통 50분정도 걸렸고 나머지 미적분 영혼까지...
-
수능볼때까지는 0
어떤 생각도 없이 그냥 공부만 해야겠다 수능 이후엔 그냥 혼자 길거리 배회나 해야지 암..
-
이메일 딱히 필요없었던거 같은데 괜히 찜찜합니다 내일 유웨이나 입학처로 연락 드리면...
-
내신은 과탐했고 수능은 사탐 치는데 수시로 경영 논술지원 가능함?
-
경외시 다 1호선인데 1호선이 악명이 워낙 높잖아요 통학하다 대중교통때문에...
-
강x 이감 빼고 없나용 96이 보고싶은데 서바강k좃같음 ㅜㅜ
-
하
-
퇴근 6
너무 힘드러
-
수학 1등급대가 수리논술 준비 잠깐 바짝하면 붙는 경우 꽤 많나요 쓰긴 했는데...
-
핀셋 넘모어렵다 1
대가리가깨져
-
고경영논 드가자 0
아빠 후배가 되어봅시다
-
07자퇴생 9평 20
07년생인데 이정도면 오르비식노베 가능한가요?
-
고논 써 말어 1
하 고민이네 높은 확률로 돈 낭비이기는한데...
-
서성한 중경외시 그 어디쯤인가요?
-
6논술 하려고 했는데 너무 쫄려서.... 하나는 교과로....
-
김상훈t 듣다가 파이널만 아수라 들으려는데 아수라하면서 유네스코 옛기출+수특 독서 병행 가능할까요?
-
전자기학 암튼그래요 나만 이 파트 못해..
-
다들 파이널기간 국어 화이팅!!
-
션티 주간지 1
최저 생각없다가 급하게 맞춰야해서 벼락치기급으로 주간지 사서 푸ㅜㄹ어볼려고 하는데...
-
아 진ㅋ자 존나자증
-
Ebook 제본 0
대성 Ebook 외부로 공유해서 제본 가능함? 안되나 션티 교재
-
아니 ㅈㅇ이 색이 이상해요 ㅠㅠ 도와주세요 고자되기 싫어요 아직 한번도 안해봤어요ㅠㅠ
-
부남 정색 4
-
나 하루 평균 2시간정도 운동하는데 오히려 더 늚 뭐임.. 1일 2딸하는디
-
시대 ta 0
시대 ta는 보통 한달에 어느정도받나요?
-
논술2장만썼당 3
ㄱㅊㅇ ㅈㅇㅇ 히히
-
dC10=시그마 i=0부터 10까지(11-iHi)^2를 만족시키는 자연수d는??...
-
성훈쌤 십지선다 사실 뭔가뭔가여서 유기했는데 시대 엣지 어떤가요? 9모 42 나왓습니다
-
고경제 고통계 고경영 셋중에 쓸깐데 뭐쓰지 흐암.
-
( 모원소 : 자원소 ) 가 1 : 0 에서 3 : 1 이 되는데 4억 걸렸다고...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.