컴공 일기248
게시글 주소: https://old.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를 선물하세요.
-
국어 고정 4등급아이 현 시점에서 뭘 하면 도움이 될까요? 수능특강 수능완성...
-
"도박해본 청소년 50% 중학교 때 시작…15%는 초등학교 때" 3
청소년 1만여명 온라인 설문…응답자 10% "친구·지인 도박 목격"...
-
진짜 하고 안하고 차이가 큰거같음 ㄹㅇ 헬스 런닝까지 갈 필요도 없고, 하다못해...
-
외대논술 15
하 외대 설캠 글캠 둘다 인문 하나씩 쓸라햇는데 이원화라 하나만된다는 얘기듣고 하…...
-
잇올에 현강다니는애들 엄청많네요 한두명도 아니고 20%이상은 단과라도 듣고 하는듯...
-
수험생 시간이 얼마나 소중한데 니네 전날에 술먹다 늦게 일어나서 버스 놓치고 지하철...
-
..?
-
211120 19
-
논술 넣을까말까 1
고민되노 흠 현역재수때도 안넣었는데 굳이? 싶기도하고 흠 생각을좀더해봐야겠군 잡생각이많다
-
[속보] 홍준표 '의대 증원 유예' 안철수 직격…"말이 되는 소리?" 4
안철수 국민의힘 의원이 '의대 증원 유예' 주장을 한 것에 대해 홍준표 대구시장이...
-
우선 김상훈 쌤 파이널 수업을 듣는 모든 현강생들을 싸잡아서 하는 말은 아니니깐...
-
이감 6-1봄 1
진짜 최근에 본거중에 가장 ㄱㅊ게나옴
-
인강컨으로 따로 준비했는데 수완 실모만 풀어볼까요
-
경희대 있다고 듣긴 했는데 다른데도 있나요...?
-
현역인데 내신 버렸어서 논술 적으려고 하고 확통은 내신해서 수능후면 괜찮을것같은데...
-
앞으로 누가 내 직업을 물어보면 철학자 라고 답하기로함 월수입 0원
-
급똥은 차갑다. 9
배변은 무엇인가? 어쩌면 인류가 일궈낼 수 있는 가장 기본적이고도 원초적인 형태의...
-
강대x 언제와요 1
시즌3 시켯는데 언제 배송 시작하나요?
-
공부나 해라 수험생.
-
점심 식곤증이랑 싸우다가 몇번 먹었는데 아니 왜 오리엔탈 드레싱 안 넣어줌? ㅅㅂ
-
1) 기본개념 실전 개념 복습 제대로 하면서 똑바로 익히셈 나는 과외 들었는데...
-
지방사는데다가 딱히 논술에 재능도 없어요 그시간에 정시공부를 하는데 낫겠죠 오늘까지...
-
반박시 명치 존나 세게 때림
-
땀이 잘 안 나는 편임 10
근데 땡볕에서 버스 기다리다 보니까 땀 ㅈㄴ남,,
-
대학 3수해서 들어왔는데 1년 휴학하고 20kg 정도 다이어트해서 건강관리...
-
문학 20번 -2, 비문학 10번 -2 비문학은 지문이 어려웠던데 반해 문제가...
-
아무리 정신차리라고 원서 쓴 게 합격이 아니라고 말해도 요즘 집중을 못해서 궁뎅이...
-
괜찮은 거죠? (본인 올해 삼반수 실패 가정하는 거임)
-
학기 중 꿀알바 과외. 이제는 잡을 수 있습니다. 과외구하는법부터 현실적인 팁들과...
-
수능만점 vs 10억 11
뭐받음?
-
히히
-
14 21 22 28 30 전 개수를 못세서 14번을 그래프 다그려놓고 틀려써요...
-
1번 2번 3번 4번 5번 6번 7번 8번 9번 10번 11번 12번 13번 14번 15번 16번
-
멀리보면 맞는게 나을거 같은데 주사 맞르면 하루이틀정도 컨디션 이슈가 생길거같은데...
-
화학 vs 지구 1
7월에 물리를 지구로 바꾼 반수생입니다. 9모등급은 원점수 기준 각각 40,...
-
사문 1등급 표점이랑 과탐 가산점 3%, 5%일때 몇등급과 표점이 비슷한가요??
-
100넘긴데가 안보이네 99.8이라지만 연치 연약도 100안넘겼고아직 생각보다...
-
메가 9평 라이브 이벤트 같은거 당첨자가 있긴 함? 공지도 안뜨는데 0
항상 궁금해서 이번에 9평 댓글이벤트 어제 당첨자 올라온다길래 계속 공지사항 당첨자...
-
수학 5등급임 18
학교수업 외에 공부는 한적 없고 2달동안 딱 3등급만 만들면 좋겠는데, 뭘 해야...
-
글리젠 뭐뇨이… 왜케 빠르냐뇨이…
-
보면 볼수록 내신 좀 딸려서 못갈것같은데 인문계열로 틀어야할까요ㅠ 작년거 보니 70퍼컷도 못들던데
-
아주대 논술 0
기계공학과 5명뽑고 자전 10명 뽑는데 경쟁률 비슷하면 자전으로 하는게 낫나요?...
-
온 세상이 봇치라는 명확한 증거다
-
킬캠 2
내가 킬캠을 72점을 넘다니
-
이미지 n티켓 1
시즌1,2 난도 다름?
-
너구리 사왔다 20
다시마랑 건더기 쳐내고 치즈랑 계란을 샤악
-
간쓸개 개빡치네 6
진지하게 문제퀄은 수특이 더 좋은듯
-
현역 정시파이터고 학교가 어수선해서 선생님께 몸 안좋아서 조퇴한다고 햇는데 자기는...
-
천코만 주세요 2
감가상각하빈다
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.