컴공 일기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를 선물하세요.
-
ㅅㅂ ㅈㄴ 헷갈리네 진짜
-
과거의 내가 너무 이쁨 빤짝거리는거 같아 뭣모르고 그냥 맨낳 즐거웠던거 같고...
-
예전에 면접 보러 갔었는데 라파엘관을 못찾겠는거임 그래서 거기 재학생으로 추정되는...
-
김승리 총정리 과제 풀다보면 8분 9분씩 걸리는데 어케 빨리 쳐내나요?
-
바보같은 질문인거 알지만 아침 7시에 독재 가서 11시쯤 집 들어오면 폰 안보고...
-
나도 내년엔..
-
평소에 살기를 중상모략을 업으로 삼고 살던것들이니 짐에게도 똑같이 하는구나
-
재미있는 사실 4
쉽다, 용이하다 등의 의미로 사용되는 '수월하다'의 어근 '수월'은 한자어가 아니다...
-
여섯시반기상도전! 15
잔다
-
현장에서 본 사람들은 뭐가 제일 ㅈ같았음?
-
총정리 과제 공약 11
1틀 당 5천덕 뿌림
-
엠스킬 한 번 들었습니다 근데 도표가 너무 약합니다 개념은 너무 복잡하게 꼬아놓은...
-
아이보리 후드안에 검은티 어떤가요 안입어봐서 모르겠네
-
수능끝나면 마저 다해야지
-
아침에 일찍 일어나게 해주셔서 감사합니다. 맛있는 야채곱창먹게 해주셔서 감사합니다....
-
였으면서 학종하겠다고 생각하고 학교선택한 중3때 내가 너무 웃김. 기가 40점...
-
어짜피 과탐 가산점 안주는 사탐 응시 가능한 공대는 사탐런 현상으로 인해 미적...
-
잠에 들자꾸나
-
2025년 09월 모의평가에 나온 공정거래법 관련 지문에 나온 문제의 1번 선지에...
-
다시 출발 14
-
현재 08년생 고1입니다. 경기도에 있는 갓반고 다니고 있습니다. 1학기 내신은...
-
회원에 의해 삭제된 글입니다.
-
악해뷰이거든
-
서른 즈음에 어떻게든 미국으로 떠야지
-
들어보신분 후기좀요?
-
sqrt3:2 4
60도로 발사한 포물선을 3등분하면 y성분과 x성분 비가 위와 같다 이게 틀린 건지...
-
전 이렇게 풂 강기원T 해설이 뭔가 저랑 방향이 달라서 다른 어떻게 푸셨나 궁금함
-
월수만가면된다 4
9월 10월 이렇게 편해도 되나요 11월이너무두렵다
-
뛰에 빨간펜이 수학과탐풀때 ㄹㅇ 맛도린데
-
수2 시발점- 수2 수분감- 수1 시발점-수1수분감 - 확통 시발점- 확통 수분감-...
-
더 늦기 전에 깨닫길 바라며 1. 도약 우리는 겉과 속이 다른 사람을 위선적인...
-
독서실 키를 안 가져왔다는것
-
내가 뭐 주장하면 허영심이니, 속빈강정이니 이딴말왜함? 5
허영 자기 분수에 넘치고 실속이 없이 겉모습뿐인 영화(榮華). 내 분수에 넘치면 뭐...
-
n제는 지문에 대한 해설지나 강의 있어서 괜찮은데 실모 다 풀고 독서 오답 할랴니까...
-
난 청개구리 10
-
모기 박멸 가능?
-
주말인데 평일보다 공부 적게 한게 레전드.. 담주는 더 열심히!!
-
다 킬러이기 때문. 화1은 근데 준킬러가 너무 많은데?
-
수학 존나 빨리푸는건 10
스킬, 발상보다 깡연산속도아닌가 마치 폰노이만 파리문제처럼
-
한지 잘하시는분들 2-3등급이 목푠데 버리는 단원 있나요??ㅠㅠ 최근에 시작해서요ㅠㅠ
-
문학은 20분초반대에 끝낸다고하네.. 대체 어떻게 이렇게 빨리 읽는거지
-
언제 하지 너뮤 하기 싫음ㅁ
-
유대종쌤 교재에 릿밋딧 너무 많음...... 지문뚫기가 상세하기는한데 그래도...
-
고2인데 수1은 뉴런했고 수2는 기출 돌리고 있는데 내년부터 수1,2뉴런 힐까요
-
윤성훈 hot7 1
인강 없이 독학으로 봐도 괜찮은가요??
-
전 아직 4권하고있음 ㄹㅇ 너무 늦게샀음 하루에 1주차씩 쳐내고있는중
-
소재별로 다릅니다. 과학기술: 수능이랑 비슷함. 수능 심화 버전 인문: 수능이랑 결...
-
투표좀 8
.
-
탁월함 찾으면 1000덕
-
기숙학원 자퇴생 7
자퇴생 받아주는 기숙학원 중에 좋은 곳 추천 좀 해주세요 비용은 상관 없어요
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.