컴공 일기248
게시글 주소: https://iu.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를 선물하세요.
-
경제관념 개 ㅆㅎㅌㅊ
-
의사는 망해도 생명과보단 잘 번다.. 자연과학은 진짜 하는거 아니다.. 대학원 탈출...
-
코어특강만 6
9평전까지 죽어라 해야지… 3,4단계 문제 진짜 어렵네요 ㅋㅋㅋㅋㅋ 하…..힘들다
-
경기도 ㅈ반고 다니고있습니다. 내신 1.33입니다 전전이나 반도체쪽 진학 희망하고...
-
이틀은 입어도 되지 않을까요
-
작년에 내한 못간거 올해 청산하려구요,, 담달에 봅시다
-
배가 아프다 3
속이 안 좋다
-
"시세 다 주고 사는 LH 매입 임대, 시장 자극 우려 크다" 1
정부가 8·8부동산대책 일환으로 수도권 미분양 주택 매입 확약과 서울 내 임대주택용...
-
솔텍 파트1에서 개념을 어느정도부터 다루나요?? 기출문제들 100% 소화했다는...
-
[단독]자영업자 배달 수수료 내년 2000억원 지원 8
정부가 내년에 2000억 원을 자영업자 배달비 지원에 쓰기로 했다. 1인당 연간...
-
이기상 썜 현강 어떰? 굳이 갈만함? 모고 하나 더 주는거 같던데
-
다 들으시나요 아니면 선별해서 들으시나요 너무 많은…
-
자러가야지 6
●▅▇█▇▆▅▄▇
-
가계부 작성 미루는중 합산된 지출내역 보면 현타올 것 같음
-
이거맛있어요 4
지에스25에서 파는건데 맛있어요
-
비밀친구 ㄷㄷ 6
-
N수생 맞춤형 밴드 ㄹㅇㅋㅋ
-
강기분 9평 전에 끝낼 거 같고 9평 후엔 이감상상 등의 실모+새기분 병행하려...
-
과학고 내신 2
과학고 1학년 내신을 메가 수능 커리로 준비해도 되나요?
-
30분동안 이래서 잠을 못자고 있는데 어케 멈춤..? 물마시기 숨참기 다해봤는데 효과가 앖네
-
논술 일정 공지했네요 참고하세용
-
주변에 입시 실패한 애들 강남대 한성대 이런 학교 진학한 애들 다 편입이 더...
-
탕탕 후루후루 3
-
고3 현역이고 이때까지 독학하다가 혼자 하다가 안 될 것 같아서 대성패스가 있어서...
-
사실 t형 4회만 풀어봤는데 이건 좀 쉬운 회차인듯용 35분 걸렸고 1개 모르겟어서...
-
86일의 전사 2
4회독 조지기
-
강기분 새기분 보충지문까지 다 돌리면 기출은 다 돌리는 건가요?(보충지문 안하면 덜...
-
흠
-
뭐 먹을까 어제는 옥동자 먹음
-
근데 그 '재능'은 선천적이기보다 후천적이여서 어렸을 때의 무의식적인 독해 경험이...
-
모솔 손!!! 32
우리 오르비언 분들은 모두 알파메일이라 아무도 손 안들거라 믿어요 ㅎㅎ
-
뭐하라는건진 알겠는데 발상을 못따라 가겠으면 어떻게함 똑같은 문제가 수능에서 나와도...
-
이거 하는 이유는 그냥 하고 싶어서!
-
https://orbi.kr/00068962835 님들같으면어케함? 막 누구한테...
-
생1 기출 질문 2
고3 현역이고 백호 섬개완, 상크스 까지 수강했어요. 기출 문제를 더 풀어보고...
-
꼭 인강 하나는 들어야하겠지??
-
. 1
-
제대 후 복학하면 26살에 2학년 되는거잖아요 그러면 2학년부턴 보통 혼자...
-
한시간동안 저거 세문제 푸니까 정신나갈거같은데 (심지어 첫번째꺼는 풀지도 못함)...
-
대성패스밖에 없어서 생1 내신대비로 대성이나 EBS중에 하나 들어야할것같은데 괜찮은...
-
국어 실모 질문 0
상상이나 한수 off 비재원생한테 파는 학원(대치) 아시는분 계신가요? +) 서비나...
-
왜지
-
지금 집가는게 맞냐
-
뇌가 과부화 해서 그런지 글이 잘 않읽힘 이건 실모 많이 풀면 해결될까요? 수학은 안그럼….
-
메렁 3
-
지인선 1회 2
통통이 6평 백분위61.. 지인선 1회 60분 2틀 나왔는데 계속 풀어도 되나요?...
-
이미 시스템 강좌에서 기출 같이 해주는데 따로필요한가요? 아님 큐뱅크로도 충분할까요
-
사문 생윤황들 1
공부 뭐하심 요즘 사탐런했는데 뭔가뭔가임…0
-
틀린 수학문제 오답할때 강의 안듣고 해설지만 보고 오답하면 0
효율 떨어질까요?? 메가 수학 컨텐츠 풀고싶은데 메가패스눈 없어서요ㅠㅠ
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??