컴공 일기248
게시글 주소: https://i.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는 필요할 것 같은데
-
참고로 밑에는 실제 gpt 답변 모음집 물론 의사경력 특유의 꽌시나 소위말하는...
-
왜 먹음 이거
-
에서 저 사람을 담당하고 있는 구밑개입니다 감사합니다
-
뭔가 편해보임 차피 평소에도 지갑 들고다니기도하고... 아 근데 얘네는 다 폰으로...
-
생명N제 추천 2
상크스. 올바원. 18모고 끝냈고 리바이벌 풀었어요 실모 전국서바랑 파이널브릿지...
-
누군가 저 때문에 성적이 오르고 목표를 이루게 되는게 기분이 너무 좋아서 내년에...
-
그분은 다 알고계신다
-
문풀하는데 얘네 좀 암기가 안되는데 걍 넘어가도 되겠죠?
-
앞으로는 헤겔 브래턴우즈 뒤로는 잊잊잊 할매턴우즈 존재감이 그냥 증발해버렸네
-
예를들어 어떤 연구에서 독립변인이 친밀도이고이를 개념의조작적 정의를 한게 대화시간...
-
3살 차이인데 .. 지금 머리가 하애져써요
-
산타느라 너무 힘들어서 오늘은 말아먹었습니다 낼 12시간 찍겠습니다 감사합니다
-
등급 낮은 사람이 (준)킬러 문제 물어보면 무슨 생각드심? 특히 수학 예를들어...
-
국어 깨달음 4
국어 뭔가 깨달음을 얻음요 그리고 성적이 꽤 안정적으로 변함 문학 ㅈㄴ 못했는데...
-
포만한 초고능아 미쳤네 11
아니 근데 매년 올라오는 전국 한자리수 씹goat들은 예외없이 물리를 꼭 끼워넣는듯
-
제발 병먹금 좀 0
ㅈㄱㄴ
-
고2 10월쯤에 만들어서 고3 개학 전인 올해 3월에 비활했는데 팔로워는 600정도...
-
그냥 문제 출제의도? 자체가 너무 ㅈ같음 전체적 배경은 식민지 근대 하층민의 생활을...
-
이로운 이해원 1
실모 이로운이랑 이해원 중에 뭐가 좋나요?? 좀 얻어갈 게 있는 거요
-
ㅅㅂ ㅈㄴ 헷갈리네 진짜
-
과거의 내가 너무 이쁨 빤짝거리는거 같아 뭣모르고 그냥 맨낳 즐거웠던거 같고...
-
예전에 면접 보러 갔었는데 라파엘관을 못찾겠는거임 그래서 거기 재학생으로 추정되는...
-
김승리 총정리 과제 풀다보면 8분 9분씩 걸리는데 어케 빨리 쳐내나요?
-
바보같은 질문인거 알지만 아침 7시에 독재 가서 11시쯤 집 들어오면 폰 안보고...
-
평소에 살기를 중상모략을 업으로 삼고 살던것들이니 짐에게도 똑같이 하는구나
-
재미있는 사실 4
쉽다, 용이하다 등의 의미로 사용되는 '수월하다'의 어근 '수월'은 한자어가 아니다...
-
현장에서 본 사람들은 뭐가 제일 ㅈ같았음?
-
총정리 과제 공약 11
1틀 당 5천덕 뿌림
-
엠스킬 한 번 들었습니다 근데 도표가 너무 약합니다 개념은 너무 복잡하게 꼬아놓은...
-
아이보리 후드안에 검은티 어떤가요 안입어봐서 모르겠네
-
수능끝나면 마저 다해야지
-
아침에 일찍 일어나게 해주셔서 감사합니다. 맛있는 야채곱창먹게 해주셔서 감사합니다....
-
였으면서 학종하겠다고 생각하고 학교선택한 중3때 내가 너무 웃김. 기가 40점...
-
어짜피 과탐 가산점 안주는 사탐 응시 가능한 공대는 사탐런 현상으로 인해 미적...
-
잠에 들자꾸나
-
2025년 09월 모의평가에 나온 공정거래법 관련 지문에 나온 문제의 1번 선지에...
-
다시 출발 14
-
현재 08년생 고1입니다. 경기도에 있는 갓반고 다니고 있습니다. 1학기 내신은...
-
회원에 의해 삭제된 글입니다.
-
악해뷰이거든
-
들어보신분 후기좀요?
-
sqrt3:2 4
60도로 발사한 포물선을 3등분하면 y성분과 x성분 비가 위와 같다 이게 틀린 건지...
-
전 이렇게 풂 강기원T 해설이 뭔가 저랑 방향이 달라서 다른 어떻게 푸셨나 궁금함
-
월수만가면된다 4
9월 10월 이렇게 편해도 되나요 11월이너무두렵다
-
뛰에 빨간펜이 수학과탐풀때 ㄹㅇ 맛도린데
-
더 늦기 전에 깨닫길 바라며 1. 도약 우리는 겉과 속이 다른 사람을 위선적인...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.