컴공 일기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를 선물하세요.
-
어려운건가요? ㅠ 현대소설 너무해!
-
. 4
-
그냥 발바닥 메타 돌길래... '팔'은 'ᄇᆞᆶ'이었는데 '칼<갏', '코<곻'처럼...
-
공통 보통 귀납법 하나틀리는데 도형 나왔을때 제외하고 미적 28 29 30을...
-
눈정화 14
-
철컹철컹
-
https://cafe.naver.com/righteacher/528?tc=share...
-
발바닥충이 와 버렸구나 이런
-
걍 자연의 섭리 거스르고 걍 떼쓰는거 받아준거 아닌가 졸려서 말 막하는중
-
파이크? 6
후반가면 좀 무서울지도 잘하자 제발 ㅜ
-
고양이 밥주기 ㅎㅎ
-
생물학적 성별, 사회적 성별 이렇게 부르기 너무 기니까 우리도 섹스 젠더 이렇게...
-
커피도 안 먹고 에너지드링크도 안 먹어서요 심장 쪽에 무리 간다고 해서 걱정되기는 하는데 ..
-
생윤 비킬러 0
킬러주제 다맞고 공맹순+예술 자꾸틏림 즉고싶다
-
지금 통합 5인데 오늘 21 나형 풀어봤더니 80점 나옴 진짜 개념알고 쎈b 다...
-
고정 1등급~만점 목표이신분들은 실모도 널널하게 다 푸시나요???
-
쉬는시간에 폰 그만할거야
-
주제 머할거임? 약간 칼럼같은거 읽어야함
-
안녕하세요 사만다 시즌3 2회 풀었습니다 질문 해주세요 0
사문러들 오세요 얼른
-
아파트아파트 5
크아아아악 노래가 머릿속에서 안나가아파트아파트 아파트아파트
-
개인적으로 “법적” 성별은 생물학적 차원으로 봐야.. 4
뭐 남자화장실 여자화장실 문제도 있고 군문제도 있는거고 여러가지로 곤란한점도많고...
-
옾챗 어캐하는겨 0
여기 올려도 됨?
-
좋나요? 안 좋은 후기가 꽤 많아 고민됩니다..
-
8강 3:0 4강 3:1 결승 3:0 가보자
-
다른 의미로 알차게 보내긴 한듯
-
BDSM 3
저기 동성애자가 10등이길래 갑자기 적어봅니다. 님들은 얘들의 본질이 뭐라고...
-
ㅈㄴ 빠름 벌써 6모 벌써 9모 벌써 수….임
-
식당 사장님들께서 배달어플 별테 당하시면 슬퍼하시는 이유를 알겠다 자느라 답 온 걸...
-
n제랑 실모 몇십개씩 푸시는 분들은 변수가 있더라도 만점에 수렴하는 1등급을 받기...
-
나 친구가 없어
-
팔로워 아깝네 계정은 걍 냅둘까
-
내 동생 영어 과외 한뒤로 거의 왠만하면 계속 1나옴 못난 오빠는 2가 간당간당한데..
-
재수생운동 2
학원끝나고 뛰어오기 계단타기 어떨까요. 갈때하니까 땀냄새나서;;;;
-
이제야 현실을 알아차린 게 허수인데요.. 찍기특강은 어디서 들을 수 있나요? 알려주세요…
-
와 그럼 이제 07..? 이 곧 현역인 거야? 07은 너무 애긴데
-
고2 수학 7등급, 공부라는 건 어떻게 하는 걸까요 3
닉네임은 국잘수망이지만 정작 국어도 잘 못하는 이른바 노베이스 고등학교 2학년...
-
시즌4와서 극대 찍은 듯
-
기출을 아예 안 본 건 아니고 어려운 4점 몇 문항 빼곤 다 봄 현재 2등급 정도...
-
지금까지 사문 실모 한 30개 풀었고 보통 40점 초중반을 진동하는데..(가끔...
-
하면 공부안해도 씹존잘알파메일이 말걸어서 인생편해질수있나
-
형 내일 바탕 풀어야 한다.
-
다들 수능 힘내요 ((((큐브에 빡치는 일 있으면 중간에 들어올 수도...
-
작년에 웨이보 아칼리로 잡았는데
-
아름답다 5
후... 드가자
-
지지램쥐요 1
예압
-
취집마렵네 3
대학가서 경영대학생을 꼬실까 의대생을 꼬실까
-
아 그냥 한 과목 유기하고 싶다..
-
학과는 어떻게 1
정하셧나요 다들..딱 와닿는게 있으셨나요?? 딱히 간절하게 확고하게 하고싶은게...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.