컴공 일기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를 선물하세요.
-
죽다 살아남.. 5
열 39.5 찍고 병원다녀옴요
-
수능 때 모자 0
머리카락 거슬려서 모자쓰고 가고 싶은데 모자 쓰고 가도 되나요?
-
붙을 수 있나요? 1학년때만 5등급이긴해요
-
그냥 제멋대로 던지고 보는말을 뉴스에서 다 집어다 쓰는거긴한데 지금 원점재검토안하면...
-
2시 기준으로 문과대 안에서 경쟁률 제일 낮던데 다들 어케 생각함?
-
작년에는 일단 1차로 거르고 -> 수능 점수로 거르고 -> 2차 면접이었는데 올해는...
-
식비 교통비 제외 형편 많이 안좋은데 많이주시는편인가
-
갑자기 궁금
-
뭐 하나 무료로 뿌리는데
-
18년도 6모 국어 [빗대어지다] 이상 없는지 확인해주실 분 0
5번 선지 [부모는 늙은이에 빗대어진다] 는 맞는 선지로 제시되었습니다. 저는 5번...
-
서강대 지식융합미디어대학 성대 미디어커뮤니케이션학과
-
최대함 4장썼는데 두장은 쓸곳이없네,,
-
9모 12123 이고 수시 포기한지 오래라 6논술 가능인데 일단 경희한, 고대...
-
사탐 공대 막은거 보셈 생각이 있음 고대는
-
공부를 아예 안 하다가 고3 때 정시 공부를 본격적으로 시작해서 지방 일반고 내신...
-
수시접수 완료 10
수시 4장이나 썼는데 이정도면 나도 수시러?
-
담임이랑 트러블 생기네.. 공부 집중도 1도 안됨
-
가뜩이나 표본 적었는데 사탐런 최대 피해까지 ㄷㄷ
-
When I #$ come down When I ^# , , , , 나 비 오 홈...
-
'국민 더 죽어야' 의대생 글에 정부 "의사 선배들이 바로잡아야" 2
'근무 의사' 블랙리스트 공개 관련해 32명 검찰 송치…"단호히 대처"...
-
최저 맞추는거보고 둘 중 하나가면 되겠죠?
-
고대 식자경 학우+고경논 2개 접수했는데 16만원 깨짐 6학종 넣으면 ㄷㄷ
-
평소에 1, 2 뜨다 결국 재수 3 뜬 02년생 틀딱인데 오늘 9모 국어 시험지...
-
강민철 커리 1
강민철 이감 해설 듣고 문학이 넘에 맘에 들어서 그런데 지금 강기분 문학만 듣는거는...
-
강민철 커리 2
강민철 이감 해설 듣고 문학이 넘에 맘에 들어서 근데 지금 강기분 듣는거는...
-
확통 공대 1
확통하고 공대 갈 수 있음? 본인 물리학과 가고싶은데 확통으로 가는게 쉬울것...
-
아 투과목할걸 5
목표가 설공인데 물1지1임... 투과목 어려울거같아서+원과목 해온게 아까워서 걍...
-
이사람 곧 뜸 6
-
다시 40분 정도를 이동해서 다른 서점으로
-
삼도극 1
수완도 삼도극 유기해도되나요?
-
높여서 걍 고논 쓸까 낮춰서 건논 쓸까 나머지 5장은 다 정함
-
얼마 맞아야 하나요
-
고려대 인문 오전/오후 모집단위 헷갈려서 서강대 생각 안하고 오후 질러버림 .....
-
부모님, 초중고 친구들, 양가친척들의 극딜을 받았었다는데 자기 진로는 자기가 정하는게 아닌감...
-
투과목 응시자수 늘었는데 특정과목이 아니라 전반적으로 늘은걸 보면 좋은상황으로...
-
얼마전만해도 기출 무용론에 리트 사설 벅벅이 여론이던거 같은데
-
설공 경치 경한 11
안녕하세요 설공(윗공대) 24학번 여자입니다. 이번에 수시반수를 고려하고 있는데요…...
-
본인 약대생임. 집에 돈들이 많은가
-
영어공부중 0
테일러 해리스 지지선언
-
서강대 경영경제 10:00-11:40 고대 어문경영제외학과 12:30까지 입실 인데...
-
23212면 평백 92가능한가요?
-
풀세트 1시간 5분 정도 걸리고 답도 예시답안이랑 거의 유사한 지점이 많은데 해볼만 한가 이거….
-
생기부에 "함께하는 작업에 좀 더 적극적으로 참여하였으면 하는 아쉬움이 있다" "팀...
-
강새기분 ebs그릿 했고 간쓸개 오프 처박혀잇는거 할지 피드백 살지 고민인데 둘중에...
-
경쟁률 존나 궁금한데
-
찾아보니까 다 구조독해파 강사들만 해설하시네..
-
뉴런vs드릴 0
휴가복귀 짐 너무 많은데 뉴런 놓고갈까
-
현강 모자 3
모자 써도 되려나요? 막 뒷사람이 안보인다거나..그러진않겠지
-
대충 공부한 애들 다 떨거지 보냈으면 좋겠다 잘준비한 사람들은 백분위 낭낭하게...
-
이 문젠데... 저는 아래와 같이 풀었는데 어떤 원리인지 저도 잘 모르겠어서ㅜ 좀...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.