컴공 일기248
백준 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를 선물하세요.
-
답지를 학교에 놓고와서 채점을 못하고 있어요...ㅠㅠ 답지 있으신 분 답 공유부탁합니당...
-
국어 3 영어 2 생윤 1 영어 1도 가능할 것 같은데 국어가 문제네요
-
근데 이해관계가 있어서 정권교체까지는 모름
-
많이 어렵다길래
-
수능이 곧 다가오면서 수능 당일날 의도치않게 부정행위를 할까봐 걱정이 되는데요 제가...
-
영어는과목취급안함.
-
수능조질게 확실하기 때문..
-
그냥 기출이나 다시 풀어야되나 그건 아니겠죠
-
질문 받아요 17
ㄱ
-
시즌 불문하고 추천 고고혓
-
반수 질문 4
거의 붙는 거 확정인 대학 있긴 한데 높은 곳 가고 싶어서 반수할 거임 근데...
-
노베 예비 고3 인데요 어떤가요?
-
수능이 다가올수록 불안감이 생겨서 오르비 들어오는 듯 3
한번 참아볼게..
-
기분은 좋구나 시즌1 2회 77점 확통0틀
-
1년 더 하면 교원대는 갈것같은데...
-
현역 9덮 총평 0
언매 89 44번 틀림ㅋㅋㅋㅋㅋㅋㅋㅋ 뭐지 독서 1틀 문학 3틀 무보정 1컷 92...
-
저는 어렵게 느껴지는데 이거 ㅈ된건가요.....
-
과잠이 옷장에 있는 옷중에 제일 예쁜데 대학밖에선 눈치보여서 못입겠음 ㅜㅜㅜ
-
한 2분은 들여다본 것 같은데 바로 가,나가 1월인지7월인지 판단 되시나요..?...
-
2등급 ㄱㄴ?
-
진짜 전 고3이라는 수식어가 제겐 평생 붙을 일이 없다고 생각해왔는데 시간이 참...
-
더 찾아봤는데 수능은 안 보이네 ㅎㅎ
-
으하하하하하하하ㅏ핳ㅎ
-
오늘의실모 1
국어 강k12회 수학 전국서바16회/이감수학2-7 한지...
-
좆같다~ 2
에휴 개시발
-
훈식쌤거는 시즌12까지 다풀엇고 엄영대쌤꺼 엄샷엄킬도 풀어봤는제 개인적으로 엄영대쌤...
-
이거 보면 낼 학교 어케 가.. 자습 감독 빡세게 돌아서 자지도 못하고 1~2세트...
-
시발 1
씨발
-
92 96 2 97 97 이면 서성한인가요? 점수 너무 안오르네요
-
이해원n제 2
이해원 n제 문제 좋나요 주변에서 다 별로라 하길래요 별로면 하사십이랑 부스터 풀생각입니다
-
개념을 많이 잊어버려서 한번 돌리려고하는데 뉴런은 볼륨이 워낙커서 시발점 한바퀴...
-
월즈에서는 제일 잘함 오늘 젠지전 믿어본다 티응갤 코 납작하게 만들어야지
-
수능날 아침에 0
예열지문 어떤거 챙겨갈 예정이신가…?
-
미역국 들고가는 거 에반가
-
공모하기에는 개인적으로도 객관적으로도 문제가 많이 아쉬워서 여기에라도...
-
100분하면 시간이 너무들어요 그리고 저는 고트가 아니기땜에 해설강의도 들어야해서...
-
궁금하녜여
-
최저라라서 국어는 진작에(..) 포기했는데 수능 당일날 아침 시간(자습 시간)에 뭘...
-
후우웅 6
뿌우 우우우웅... 뿌에엥
-
그런거 없다구웃!...
-
이 문제가 "나올정도"??? 이문제가 "시험에 나올 가능성" [자주 나올 가능성]...
-
예비 고3인데 0
심찬우 선생님 커리 타고 싶은데 2026수능 커리큘럼..? 교재? 언제 나오나요
-
포켓몬 빵중에 1
초코 롤케익 이거 맛있음?
-
이왜진? (상호 합의 하에 계약 종료)
-
제목 그대로 오르비 뱃지는 어느학교부터 받을수있나요?
-
동사 토욜마다 시대가서 서바풀고있고 최근 서바나 더프는 50아니면 47정도...
-
24수능 기준 국어 2컷 수학 96점 영어2 과탐 둘다 2등급 상위 +약수 꼬리라도 되는 곳있음??
-
반수생활과 함께한 이 커플이 드디어 사귀는구나 계약동거는 GOAT다
-
세포분열 각 시기마다 사이클린과 cdk가 합성과 분리를 반복한다는데 그러면 시기가...
-
해모 같은 시대북스 거 팔려나
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.