컴공 일기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를 선물하세요.
-
오렌지 젤리다
-
생기부 다시 보고 있는데 지금 보니까 미2 세특에 기벡 내용을 적어놨네ㅋㅋㅋㅋㅋ
-
조언좀요ㅠㅠ재수생이고 국어 공부 거의 안하다시피했는데 사설은 쭉 잘봤어요 그러다가...
-
학교에서 1학기 때 동아리까지 하다가 기습반수인데 어쩌다보니까 근황을 거의...
-
물리 커리 추천 11
vip 삼순환 역학만 이순환까지 끝냇는데 이제 뭐 하면 좋을까요? ㅜㅜ
-
잇올 비싸서 못듣고있는데끊고 현강 다니고싶어여
-
아까전에 그 글 보고 화가 많이 났는데 삭히곤 있었는데 13
불행 포르노같아보일순 있는데 지방에서 낡아빠진 방바닥에 구멍나서 공구리 셀프로...
-
잇올 다니고 거리도 조금 있어요 지하철타고 총 40분거리인데 9모이후 그냥 차라리...
-
굿굿굿굿굿굿굿굿 1
Good
-
화학 고수들만 41
ㄴ선지 구할수 있음??
-
1.건동홍숙 이상 공대 지원에 유불리 심한가요? 2.메디컬 목표면 안 하는게 맞죠?
-
패드가 없어서 그냥 안 써요
-
우리반친구들은 자기들 작년반 친구들하고 먹고 내 작년반친구들은 본인들 반친구들하고...
-
진짜 가격 존나 선넘는거같은데 식사 시간 절약하려면 어쩔 수 없어 보여서,,,
-
제이팝이 미래다 7
ㅇㅇ 개성넘치고 가사도 좋고 다좋음
-
이로운 3회 4단 n축 11
카르텔;;
-
조정식이 피뎁충들은 사회에서 걸러진다 12수해도 원하는 대학 못간다 이러는데 본인은...
-
10% 이상 증원한 경우에만 재인증 받는거면 9.9%씩 5년동안 증원하면...
-
얼마전에 화작으로 바꿔서 11문제 한 세트씩 시간재고 푸는 연습을 해보고 싶은데...
-
올해 3번째 수능 준비하는 사람입니다. 원래 ~~하면 뭐 가능? 이런 거 물어보는게...
-
6모 88 7모 92 쩝 …. 평가원이나 교육청 모고 싹다 88~92에서...
-
그 특유의 쾌감을 잊을수가 없다 야심한 밤 공부끝나고 밤에 집걸어가면서 느끼는 쾌감...
-
의대생들은 n수해서 들어오는 경우가 많고 여기다가 타학과랑 다르게 6년에다가 군의관...
-
고소당해야됨
-
영어 3등급 목표면 최대한 쉬운문제들로 어떤거 어떤거 풀어야할까요? Ex) 듣기 +...
-
세상의 소식을 알려주는게 아니라 공식 언론사가 말아주는 말세 특집 이런거 보는느낌이 심해요….
-
올해 수능 말고 내년 수능부터인가요?
-
쇠로 만든 고기를 어떻게 먹죠?
-
수학 N제 고난도 문항은 잘 푸는데 실모만 치면 점수 안 나오시는분 12
있나요..? 이런 경우면 어떻게 해야 할까요..
-
컴공 일기248 0
백준 1937 DP / DFS 융합 문항 풀이 소감 : 본질은 DFS인데, DP의...
-
올 사설 난도 0
어느 쪽임
-
이해원님 설명으로는 시즌2가 시즌1보다 살짝 어려운 정도라던데 풀어보신분들은 체감 난이도 어떤가요?
-
언제 풀어야할지 어떤식으로 오답해야할지 아무것도 모르겠다 ………
-
너무너무 어려운데 내가 진짜 개못하는건가.. 아니면 문제가 많이 어려운걸까… 풀어보신분…
-
뭔 ㅂㅅ 같은 주제에 대해 옳소 거리고 있는 프사 보면 9
다 애니프사네
-
언젠가는 먹으러 가겠지 너무귀찮다
-
본인 수학 노베고 7등급에서 4등급?으로 2달만에 올림 .. 개념도 다 잘 아는 것...
-
싸우면 짱먹을듯
-
괜찮나요? 이감 상상은 다 풀었어요
-
요즘 이거만 ㅈㄴ 들음 개신남
-
병실에서 신지가 하는짓 제외하면 흥미롭게 봤음 은근 호불호 갈리더라
-
푸틴, 결국 핵 꺼내나…'서울 2배' 러 침공, 우크라 '초유의 도박' 4
우크라이나의 러시아 본토 침공이 15일째 이어지면서, 개전 2년 반만에 '전쟁...
-
7일차 D-86 1
9시에 퇴근하고 어제 보다만 한국사 마저 봣네요. 아이패드로 한국사노트 만든거...
-
정말 똑똑하셨는데 단점이 너무 똑똑해서 보통 학생들이 a라는 포인트에서 고민하면...
-
실모 벅벅도 좋지만 기출 한번만 더 보면 어떨까요 다만 의도적으로 이해를 배제한...
-
진짜 볼때마다 개웃기네
첫번째 댓글의 주인공이 되어보세요.