컴공 일기248
게시글 주소: https://i9.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를 선물하세요.
-
으하하하하하하하ㅏ핳ㅎ
-
오늘의실모 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가 합성과 분리를 반복한다는데 그러면 시기가...
-
해모 같은 시대북스 거 팔려나
-
그 대충 이만큼 평행이동 한거겠지 ㅇㅈㄹ하고 하면 대충 거의 됨 ㅋㅋㅋ 이게...
-
이제 막 시발점 수2 끝냈는데 바로 고3 자이스토리 가능한가? 좀 빡세려나?
-
예스24 알라딘 같은 데
-
안녕 오르비 5
-
이번엔 좀 귀한 걸 들고 왔어
-
부탁드려요 시즌포함해서..
-
거미 죽임 0
에프킬라로.. 애가 처음에 에프킬라 뿌렸을때는 도망가기 바빴는데 나오자마자 진짜 개...
-
15분 5 4
7
-
우울하고 눈물나는건 어쩔수없는거겠지 ㅅㅂ
-
수능수학 개꿀팁 5
모든 번호는 조화롭게 나온다
-
일단 윤석열이 좋빠가로 4500 수시합격 발표까지 버틴다는 전제하에 내년 3월까지...
-
평가원은 2등급 안에서 백분위 왔다갔다 함 강x 시즌4는 60점대 후반에서 70점대 중반 나옴
-
폰연등은 안되고.. tv로도 볼 수 있나요..
-
”군대“다 남자들 명심하도록....
-
이 순정을 니들이 알겟니
-
수능 전까지 구입처, 커뮤니티, 맥주 고르는 법, 참고 서적 등등 알고 싶으신 것 있으신가요
-
06이고 수학 4~6 이런식으로 뜨는데 정승제 정상모 정병호 등.. 기본개념 부터...
-
선택과목 0
약대 목표인데 수능날 등급 화학2 생명2 vs 사문1 생명 1 나온다고 치면 과탐...
-
티젠전 진짜 개맛있겠다 13
흐흐흐흐
-
전교생이 200명인데 국수영 모고 고정 1 아니면 가끔 2초 하는애들이 20명정도...
-
다들 알고 있을진 모르겠으나… 몇가지 꿀팁을 적어보자면~ 첫번째) 일찍 가자....
-
1인형 독서실인데 방금 책 뒤쪽으로 들어감 미친거 아니냐 와.. 책 진짜 끝까지...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.