컴공 일기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를 선물하세요.
-
고때 고2 여서 러셀 모의 수능 끝나고 들어가봤는데 진짜 분위기 초상집마냥 와......
-
국어 98 수학 98 영어 2 생명 99 지구 95 지구랑 영어가 제일 자신이 없어요 ^.^,,
-
그런 게는 다 죽어야함 반갑습니다. Team KUKLL 입니다. 이번엔 현대소설...
-
또 허수들 유입을 차단하는듯..
-
외대 가천대 세종대 이렇게 넣으려는데 셋다 수능 일주일뒤에 토 일 월 순서로 있는데...
-
저녁 2
-
국수영탐탐 99 100 2 98 96받고 해피타임보낼듯
-
저희 영어쌤은 철저히 본문무시파이셔서 모의고사 지문을 더 중요하게 여기십니다. 보통...
-
교과 인천대 전자공학 (지균, 과하향) 세종대 자유전공 (지균, 적정) 인하대...
-
이겨도 ㅈㄴ 까일듯
-
오만과 편견 1
에서 편견을 맡고 있습니다. ㄹㅇ 없던 편견도 생기겠다..
-
고대 인문논술 지원했습니다. 논술 준비해본 적 한 번도 없고 오로지 최저 높은 거만...
-
6모등급 22269도 있고 21144도 있네... 설의 최저충족이 생각보다 적은 이유가 있음
-
그래도모르니까 보험용?
-
1학년때 코로나로 골골대면서 시험봐서 국어 7등급 하나가 나왔는데 최종 등급은...
-
수시 5
지방일반고 내신 2.8정도인데 모고가 6모 12233 9모 11111이라 그냥...
-
언매확통 24222 숭실대 되나요?? 93 66 낮2높2라 쳤을때요
-
6모 84 나머진 저정도 나오는 영어 1 의대최저러인데 ㅠ 파이널만 들으면 그불구랑...
-
설맞이 pdf 캡처해서 질문하네ㅋㅋ 깡이대단함
-
물리학1 킬러문제 삽화 19
-
3합4 1개 넣을지 2개 넣을지 고민입니다 약대 목표로 삼수중이라 일반과는 답 없는...
-
꼬기 긍장 3
소주 4병장도 마샸다!!
-
굳이 결혼 안하려고 함??
-
주요과목 내신 2.47에 생기부는 그나마 자신있어서 상향 지르는 카드로 홍대랑...
-
성대 예비 1번 떨 건잡다니는중
-
달리면 그제야 자러 가겟소 (살짝 고전시가 느낌)
-
오노추 0
르세라핌-good parts
-
대 역전극.
-
만약 그렇다면 모르게하는법 있나요
-
이런! 벼락을 맞고 죽어버렸어요 ㅜㅜ
-
뿌듯허다 6
오늘 목표한거 다 끝냄 강기분 문학 두지문 검더텅 영어 한 유형 끝내고 수분감...
-
최저꼬라지가 2
4합 5 3합 4 3합 5 3합 6 이러네 아 제발 정시로 가자
-
미친듯이 싫음 시간이 너무 빨리 지나가네요 고등시절이 가끔 주마등처럼 스쳐감 그리고...
-
히게단- 제로인채로 있었더라면
-
( 여당 대표, 2025년 의대증원안도 협의 시사+"전제조건으로 안되는 건 없다." ) 0
https://www.hani.co.kr/arti/politics/politics_g...
-
21번에서, 도함수 적분을 활용하면 조금 더 간단하게 풀리네요 도움됐으면 좋겠어서 올려봅니다..!!
-
제 공시의 비결은 메디키넷 + 하루에 정신과 약 7개 복용의 부작용으로 배가...
-
메가 캐스트 0
불꽃쌤 볼때마다 궁금한건데 댓글에 키링키링키리링 이러시는분들은 뮈하시는분들이셔요?
-
고2 학평때 아얘 노베였는데 39점 받고 2등급떴음
-
현재 위치보다 목표는 높은데 별 핑계대면서 공부는 안하고 괘씸한 날강도 심보에...
-
성균관대 의대 3
써 말아... 올해 증원 진짜많이 되어서 안쓰긴 아까운데 나같은 평민일반고출신을...
-
어떡하지...?
-
D-65 1
-
개념만 깔짝깔짝 보고 풀만한 문제인가요? 제시문 2번입니다
-
사람들이 그냥 서연고 서성한 이래서 그냥 쫘르륵 있는줄알았는데 아니었네...
-
[26] 삼가 뜻하는 바를 아뢰오니 -> 추가 [41] 관동별곡 -> 꽤 큰 개정...
-
난 오르비만 하는데..
-
군대까지 다녀오면 넉넉잡아 28살인가.. 그때까지 인연을 만날 수 있으면 좋겠네요...
-
멸망하나요... 뭐풀어야하지 딱 2컷 걸치는상황입니다 실모 벅벅할까요...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.