컴공 일기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를 선물하세요.
-
그냥…. 3
그냥 논술로 대학가면 좋겠다.. 수능 얼마 남지도 않고 하니 지금 하는 게 의미있나...
-
윤사 23
고정1 이신 분들 공뷰 뭐뭐하셧어요?
-
ㄹㅇ
-
하루에 총정리 2개씩해도 다 못함ㅋ
-
뭐이리 잘함?
-
16롤드컵 SKT T1대 락스 경기가 갑자기 생각남 4
그때 서폿미포 진짜 충격이였는데
-
라고 생각해보니 지난번 문학에서 개 말아먹었던게 생각이 난다 화작은 랜덤이고 문학을...
-
걍 아예 성별이랑 사/과탐 다 바뀌나? 진짜 모교가 젤 가깝긴한데 작년에도 좀...
-
수학 5->3 2
9모 52 맞았는데 남은 기간동안 열심히해서 3까지 가능할까요.. 낮3정도 지금...
-
비추??
-
어디임 님들은?
-
내년도 수능 보려고 해서 알아보다가 메가는 너무 비싸서 대성19패스 사전예약 했는데...
-
저격은 아닌데 5
수능앞두고 장문 사연 읽지마셈 솔직히 누구나 사연은 다 있고 읽는데 시간 아까워...
-
실모는 왤케 21을 어렵게 냄?
-
조때따 조때따 조때따 ㅋㅋ
-
킬캠 풀고 있는데 가끔은 등급컷 나오는 모고도 볼 필요가 있을 것 같아서요..!...
-
오르비 듣보 1인 수능 후에 돌아올게요(겁나 긴 장문주의) 5
이제 수능도 20일 안 남은 상황이고 밤중에 감성빨로 글 한 번 쓰고 싶기도...
-
ㅊㅊㅊㅊㅊㅊㅊㅊㅊㅊ좀 ㅊㅊ좀
-
포만한 6
four만한 five만한 오만한 오만한 포만한 푸하하
-
저는 공부하러 가서 조용해지겠습니다 내일 아침까지 오르비에 돌아다니는(공부 질문글...
-
화작n제 2
이감 화작n제 어떤가요 다른거 좋은거 있나요?
-
사만다 개좋네 0
나 이거 왜 이제삼 ㅋㅋ
-
지금부터 정신 차리고 공부해도 기적이 일어나지 않을거라는건 압니다.. 그래도...
-
떨치고 자야지 5
다들 군밤
-
요즘도 양적관계가 더어렵나요?
-
환급대학 붙으면 패스비용 100%+교재비 50% 너무개꿀이였어서 다시는 안나올듯 ㅋㅋ 예상댓글
-
언제나 그렇지만 어떤 정의를 만들어도 그 정의에 딱 맞지 않는 경우들이 있다....
-
지금 안사면 라인업 공개되면 19일 때 안산거 개후회될거 같음 신규강사 국수영 다...
-
아니 대체 왜 이걸 어케 알아 아냐 알 수는 있겠지 그치만 억울
-
짱친이었다가 원수되는 서사 너무 맛있고 작화도 개지리는데 망한게 너무 아쉽다
-
천덕 드릴게욥 알려주요
-
N제 푼게 이거밖에 없어서 난이도를 몰라요. 핀셋 과목별 N제랑 비교해주세요. 보통...
-
피곤하당
-
거의 못봄
-
현역 10덮 45분 100점 (나머지 과목도 다100 화2 47) "간만에 더프에서...
-
민주주의적 관점에서 권리를 위축시키니 잘못된 행동일수도
-
진짜로?
-
굉장하네요
-
과거사 문제 청산하고 이민자 더 많이 받아들이게 되나요? 입헌민주,유신의...
-
오늘 하루도 알차게 공부를 할 수 있어서 감사합니다 산책하다가 개울가에서 오리를 볼...
-
실친들 대화중인데 C. (롤 얘기중)... ^888488^도 쫄리고 북미 상대로...
-
물리(기계공학)으로 박스 껍질 도배
-
다행히 딱 맞게 사논듯
-
N/반수생들 대상 질문 19
만약 올해 수능 잘보고 대학 옮겨서 성불하면 탈릅하나요 아님 내년에도 있을 건가요
-
마스터피스 0
션티쌤은 제로가 쉬운편이라는데 왜 난 원보다 제로가 어렵지 제로 1회 89 어려움...
-
기만.. 3
이제부턴 공부에 집중하기만..
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.