컴공 일기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를 선물하세요.
-
30살이랑 대화를 하면 어떤 말을 하고 싶으신가요? 16
님들이 20살이라고 가정했을때
-
제목그대로 연대 논술에서 전기전자랑 신소재랑 합격점수 컷 차이가 어느 정도 돌까요?
-
지금까지 뭐가더 어려워요 저는 전국이 더어려운듯
-
지금 과외샘은 그냥 처음보는 문제 슥슥 플어주시는데 개인적인 과외샘 태도?가 맘에...
-
보겠죠?
-
아수라 들어도 됨?
-
그냥 약대도 그렇고 일반과도 상대적으로 낮아보이는데 과학논술폐지고 최저없으니까...
-
나때는 화학이 근소우위였는데 이러면 화학은 백분위가 진짜 터지겠네...
-
이감 하반기 남은 2회분 이감 파이널 패키지 상상 파이널 패키지 김승모 3회분
-
졸업시기 7
14년 2월
-
진짜 열심히 해야지
-
학생부 교과 [일괄선발] 학생부 100% 라고 전형에 적혀있는데 이는 1배수를...
-
서바 10회 0
넘모 어려워서 시간끝나자마자 덮은다음 유기했따
-
영차 영차 (크로녹스 아스트라 보는중)
-
고경은 확실히 3
쓸사람들은 미리 다 쓴느낌이네 논술 경쟁률 61.44>71.50
-
강대k 19~32 강대x 1~16 킬캠 1~12 빡모 파이널 시즌3,4 6회분...
-
큰 돈이 새는 걸 막는 길입니다
-
물리 붐은...온다...
-
맞나여? 수시논술 쓰려구여
-
나머진 투가산이랑 지2로...
-
고대 서류제출 우편으로 할 수 있나요?
-
서울대 고려대 연세대 서강대 서강대 성균관대 Let's go!
-
올해 물2화2 "이상치"임
-
솔직히 대박까진 안바라고 사고만 안났으면좋겠어요
-
있으면 추천 부탁드리겠습니다..!
-
나만 그렇나..
-
이걸 이제서야 듣다니
-
사탐 선택과목 1
친구나 주변에서는 등급따기 쉬운 생윤이나 사문같은거 선택하라고 하는데 저는 쌍지...
-
검정고시현역붕이는다른거못써~
-
고려대학교 수학과 / 기대모의고사 9년차 저자 대학재학시절 수능(평가원) 현장응시...
-
클난건가
-
솔직히 0
고전산문이나 소설이 연애 관리스토리면 설레고 재밌어서 읽는게 행복함 문제도 잘풀림
-
6,9평보다도 너무 많이 늘어난거 아님??? 진짜 일가친척 느낌 나는데
-
강대 x 기하 0
이거 사면 서킷도 같이 오는건가요? 보니까 서킷은 기하 없던데… 너무 돈낭비 아닌가,.고민되네요
-
짜증나게 하지말고
-
수시 논술 넣으려고 하는데 피어싱 착용한 상태로 수능원서사진을 찍었어요. 이거...
-
제발 2기를 내주세요 (발표확정 없었음)
-
118000원 흑우.. 19
제 책 개념편, 문제편까지 컬러로 인쇄하니 사장님이 어? 이러면 책 값보다 더 나올...
-
이거 가능임? 7
서강논 11시 40분에 끝나는데 현실적으로 건물나가기+폰받는거 감안하면 또 10분...
-
어려운 19-20번으로 나오면 그날 실모 운영 개족치는 그냥 개Joat ㅋㅋ
-
무친 비염 0
환절기라 비염 땨문에 공부 집중 안돠네..
-
칩찬승가자
-
2/6 5
최저만 맞추면 가능성 있다...!
-
홀수번만 풀까 ㅇㅈㄹ ㅋㅋㅋㅋ
-
문재인파업때 의뱃 오르비언들만 봐도 무슨 비의대생들 계몽시키기 하는 줄 윤석열때가...
-
많나요
-
ㅇㄱㅈㅉㅇㅇ?
-
수험생들의 생각은? 전자는 ㄹㅇ 수험생부모한테 칼맞는거고 후자는 ㄹㅇ 대한민국 멸망하는거고
-
의대논술 질문 4
과탐 안보는 학교가 있나요? 생1생2가물가물해서 수학으로만 갈 수 있는 의대논술이 있는지 궁금합니당
-
빡모 0
9평 반영이라길래 쉬울줄 알았는데 뭐지...? 1회는 킬캠 어려운 회차랑 비슷하네ㅋㅋㅋ
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.