컴공 일기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를 선물하세요.
-
남자분들 쪽지 그만보내세요
-
너무 높은 산처럼 느껴짐...
-
무슨 누구네 대학이 누구 대학보다 낫네 해도 전세계 랭킹은 사실 다 비슷비슷함…....
-
분명 일주일전까지만해도 되게 의욕넘치고 목표의식이 있었는데 사흘전부터 걍 다...
-
이대 약대 주면 5
기어서라도 갈듯
-
소신발언 0
성적도 지방약>여대약대 아님? ㅋㅋ 이게말이되나
-
도대체 저분 정체가뭐지 25
건동 떨어지고 이대붙은 농어촌 반수생이 중대를 논하면서 이대 올려치기하는 이 상황을...
-
2호선임 동의시 개.추
-
ㄱ이 왜 틀렸는지 궁금합니다. 가시광선 영역은 좀 다른가요?
-
다들 다 놀러오는곳에 공부하러 간다는게
-
물어볼거잌ㅅ어요‘ㅜ
-
그냥 축제임
-
인스타보다가 1.4999… = 1.5 에 대한 논쟁이 있는걸 보았습니다. 고3...
-
진짜 무서운건 2
어그로 컨셉이 아닌 것 같다는 거임..
-
3합7 현역 0
현실적으로 많이 어려운가요...? 3합5도 썻는데ㅠㅠㅠㅠ
-
작년도 핵빵난 과 지원했다고 가정하는 노스트라다무스 전형임
-
입학하자마자 자기 수능성적 까먹는거보면 치매 초기증상인듯 하고싶은말: 야식추천좀
-
김기현 아이디어 3
고2 9모 낮1인데 내년에 아이디어 현강 들을려는데 쉬울까요..? 적당한 난이도의...
-
수학 2컷 (백분위 89-91) -> 연세대 후자는 수학을 안 보기 때문에 이미...
-
좀 놀라운게 0
'이=건이 아니다' 라고 주장하는게 아니라 '중경외시이가 커뮤에서만 쓰는 말이다' 라는 거임..
-
인스타 스토리올린거 보니까 카페에서 공부하는데 누가 자기 92학번 선배님이라고...
-
내일 점심 추천좀
-
애초에 둘다붙으면 이대갈애들이 그대학을 그냥 쓴거라는 말이 있던데 진짠가 ㅋㅋ
-
수시 문제점 1
경쟁과열화 줄인다고 5등급제 했지만 짜피 대학에선 원점수하고 학생수 고려해서 등수로...
-
기적가능?? 3
6모 54423 (수학 4컷) 9모 아마 54433 (수학 4컷) 9모 이후부터...
-
남자는 왜 여대 못가나요?
-
수학 슬럼프 0
원래 개잘풀렸던 문제들이 갑자기 며칠전부터 안풀리는데...
-
https://namu.wiki/w/%EC%84%B1%ED%8F%AD%EB%B2%95...
-
진짜 모름 ㅇㅇ
-
풀 거 필요한데 아수라일지라도 교재만 사는 건 좀 별로인가요.....
-
시험칠때 (작수때도, 항상) 딴생각은 기본으로 들고 머리에서 노래 맴돌고 그러는 건...
-
역시 고대 오기를 잘했다 우리의 함성은 신화가 되리라 요약 : 님들은 서울대나 의치한 가세요
-
왜 그러지
-
초면에 욕 박는거
-
고3 체육시간에 뭐함? 고2하고 똑같나
-
낼부터 수학 풀면서 뇌 좀 써야겠다 하루에 수학 50문제 씩 풀기 도전
-
여긴 뭘 하는 곳일까요
-
으차 4
-
어떻게될까요 현실적으로 올릴수있는정도가…. 국어는 높3이었는데 23313은...
-
현재 일반고 현역이고 수학 2등급이 목표입니다. 6모 65 9모 76 킬캠s1 74...
-
중학교때부터 입시 전략짜고 3년 로드맵 대강이라도 쫙 짜긴 하더라 뭐든 준비된 자가 승리하는 듯
-
사문 계층 질문 4
모래시계형 계층 구조가 수특에선 가장 적은 비율의 중층,소수의 상층,다수의...
-
공부는 하게 해 줘 제발 의사 안 해도 되니까
-
이제 아는 건 다맞는데 모름or헷갈리는게나온다? 걍 무조건 틀림 하. 그래서 계속...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.