컴공 일기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를 선물하세요.
-
헤헤 독재가는중 2
에헤라디아
-
지1도 20,21수능때랑 다르게 엄청 난도가 올랐는데 3
이래서 사탐런 사탐런 하는구나..
-
있었나요? 기억이 잘 안나서… 두개 대립유전자가 연관된 염색체에서 비분리 일어나는 유형 있었나요?
-
ㅋㅋㅋㅋㅌㅋㅋㅋㅋ아 미치겠다 진짜 어리게 봐줘서 고맙습니다 !
-
한자칸에 걍 이름써버리고 냈는데 불이익 있나요?
-
2025학년 대비 경북대학교 전문 논술 강의 안녕하세요! 경북대학교 전문 논술팀...
-
권당 2만원에 팔아요 ~ 비닐만제거하고 펼쳐본적없는 새책입니다
-
섬착순함명
-
개념에서 틀리거나 개념에서 시간 끌리고 도표 못풀거나 결국 개념인듯 다 아는 사실이라면 ㅈㅅ
-
전형료 개비싸네 0
장난하나
-
코스프레하고 있으면
-
12번 16번틀 도표 다맞추고 문화파트 틀려버리기~~~
-
여캐투척 4
이제 슬슬 공부하러
-
1-1 풀었는데 생각했던거보다 매우 어렵네요
-
6번에 ㄱ선지가 오답인 이유는 플라톤과 아리스토텔레스 모두 동의하는 진술이라서가...
-
사실 엘리트계층에 포함되는 정치인들봅시다 바이든 명문대안나왔고 펀쿨섹 명문대안나왔음...
-
연논 한논 1
수능 안봐도 치러가도 되는거 맞지요?
-
최소 시간으로 걍 안정적인 2 유지하는게 맞음 아님 1로 올리는게 맞음 3합7...
-
아예 노베는 아니고 23-26번까지는 풀 수 있음 27-30번까지 맞추고 싶은데...
-
내 모교가 여고였었구나 22
-
문득 궁금한점 0
여대 축제는 외부인 들어갈때 남자도 들어갈 수 있음?
-
언매 1등급 (백98) 미적 2컷 영어 1등급 생1 1컷 지1 2컷 이러면 아무래도...
-
똥 4
점심먹고나면 똥이 꼭나옴 수능날어캄 ㅠㅠ
-
외대 간판학과 아닌가
-
씨?발 3
♡
-
자리 책상에 이름 붙어이ㅛ어요?? 아님 자유에요?
-
논술은 다들 쓰셨나요 11
-
냥대 수리 2
작년엔 기하러였어요(올해는 미적) 9모 기준 2등급 나왔지만 안정적인 2등급대는...
-
맛점! 6
-
근데 진짜 인간관계가 전무한 사람은 가끔 본적 있음 11
그래도 가족이랑은 같이 지낼테니 가족은 빼면 학교에서 인간관계가 말 그대로 0인...
-
주식공부 마려운데
-
조선족에서 바로 선족 선족 겜망치는 리선족생각남 ㅅㅂㅋㅋㅋㅋ
-
수시도 접수기간 거의 끝났는데 정부쪽이 유예하겠다는 의지를 전혀 안보여주고 있어서...
-
원아이드잭님 논술 강의 다른곳에서 볼 수 있는 곳 있나용?? 몇년만에 접속햇는데...
-
원서접수 1
이렇게 뜨는데 이거 제가 뭐 해야되는건가요?ㅠㅠ 수정할게 없는데 수정이라 떠요ㅠㅠ
-
프사 변경 완 8
히히 프사 필요하면 주워가세요
-
두번 연의논술로붙고 두번 자퇴하면 빡칠거같긴해 ㅇㅇ
-
수능<<~~이3기 공부 언제함 진짜 ㅁㅊ겟음;; 선거끝나면 30일 깨지네
-
공통만해서 12(계산실수) 13 14 20(계산실수) 21 22 이렇게 틀린거면...
-
진짜 개 잘 풀듯
-
(흩어진백골을주우며) 명수야, 내자식아! 이 토막에서 자란너는 백골이나마 우리를...
-
올해설의갈게 ㅋ
-
운동하세요
-
이중차분법 같고 막 그럼 워치시계 도어문 이런 느낌임...
-
아직 1:1인곳도있음
-
본인이 왜 재수하는지 뭘 목표로하는지 본인이 왜 원하는지 그거부터 똑디하고 그러면서...
-
유도선도 못보고 냅다 끼어드는 새기들이나 우산으로 눈 앞 가리고 냅다 차도로...
-
인간관계가 디씨(수갤) 오르비 오피지지(롤커뮤)에 한정되어있는데 정상이죠? 13
그쪽에서는 어떻게 생각하실지 모르겠지만 저는 나름 그분들이랑 친밀감 느끼고...
-
맞췃다
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.