컴공 일기248
게시글 주소: https://old.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시간 동안 스터디윗미
-
하아 도파민 과다분비 돼서 잠 못자고 여기까지 와버림
-
아니 어떻게 “다음주” 목요일이 수능이야
-
역대급 캐리판 ㄹㅇ
-
페이커 저 새끼 45세트에 한 것보다 더하라고? 오히려 슌 엘크가 45세트 뒤지게...
-
오늘 실모 보실거임?
-
월즈오면 LCK팀 응원할수밖에없음 ㅋㅋㅋㅋㅋ
-
근데님들 만약애 21월즈때 티원이 담원꺾고 올라갔으면 3
그때 EDG이겼을거같음?
-
4세트 엘크가 성장잘한거 집어던져서 5세트까지 간거고 5세트 빈 느낌없고 온 똥구멍...
-
공통 다 맞을 수 있겠다는 근자감이 드네 ㅋㅋㅋ 제발 25수능수학 공통1틀 미적...
-
ㅅㅅㅅ
-
7번이 진짜 딱 좋을듯
-
닉변완. 3
-
쓰리핏 탐나네 ㅋㅋ
-
ㅈㄴ 무서운데?
-
스킨 후보 10
ㅇㅇ
-
린킨파크 한번만 봐준다 ㅋㅋㅋ
-
-
아진짜못참겠네 4
헤으응
-
월즈 스킨 예측 6
우스우스: 그라가스 오 너는 최고야: 신짜오 신: 갈리오 or 아리 or 사일러스...
-
나만 그런거 아니지? 걍 지금 씻고 독서실이나 갈까..
-
수능은 티원처럼 7
수능날에 최고점 찍자고
-
캬
-
어 상혁이형이야 0
.
-
건국대 1
건국대 자전 추합 몇번까지 빠질 것 같나요??
-
-
뭐해? 1
올려
-
실모 풀었는데 둘다 3n점대 나와요...ㅎ ㅠㅠㅠ 수능때 2등급이라도 받고싶은데 걍...
-
아예 버려도 괜찮나요 ?? 이거 버리면 남은 문제는 다 맞아야 하는데 요즘 세포분열...
-
지들 졌다고 시위하는건가 추하네 좀 ㅋㅋㅋ
-
초딩 때부터 게임대회 관심 생겨서 응원했는데 16년 우승보다 지금이 더 기분 좋음...
-
4시드 미드 십캐리 결승 패승패승승
-
23년 3세트 징동한테 무난히 끌려가다가 질뻔한거 토스로 세계선 바꾸고 24년...
-
-
럭스한적있음??
-
아 개귀엽네ㅋㅋㅋ
-
1사람당 10만덕 댓글 ㄱㄱ혓!
-
대가리 깨러간다 뭐? 국제전 7년 무관? 뭐? 물로켓? 응 월즈리핏 ㅋㅋ
-
초중반 운영은 blg가 훨씬 잘한 것 같은데
-
아 몰라 대상혁 5회 우승 라이브로 봤잖아 한잔해 ㅋㅋㅋ
-
역2롤 t1 faker
-
이래도 까?
-
둘 덕분에 이겼다 ㄹㅇ
-
ㅅㅅㅅㅅㅅ
-
UP
-
시이이이발 대상혁 대상혁 대상혁
-
롤켜야지 0
달려
-
1세트랑 3세트는 진짜 피말려뒤지는줄알았음
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.