컴공 일기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를 선물하세요.
-
마지막 파이널로 정리해볼까
-
점메추 해주세요 2
혼밥 10000원 이하로요 평소엔 버거킹 돼지국밥 돈까스에 가끔 마라탕먹고다님
-
준 or not 0
-
총정리과제 아직 배송 안 왔는데 1주차 들어도 ㄱㅊ은가요? 걍 교재 오면 듣는 게 나을까요
-
김승리 아수라 강의 듣고 있는데 학습계획 보니까 실모 일주일에 두 번씩 풀라고...
-
독서 -3점 문학 -5점 언매 -5점 요즘 계속 35 36 연달아 틀리네요....
-
하니한테 2
매주 정벽모 1회차씩 숙제내주고싶다
-
9모 6모 둘다 백분위 87 높은 3입니다…. N제나 브릿지를 좀더 해야할지...
-
안녕하세요. 독서 칼럼 쓰는 타르코프스키입니다. 수년간 국어 과외를 하면서 국어...
-
그대들은 4
-
뭔가 일침 놓는 가사라 공부자극도 됨 ㅋㅋㅋㅋ 팩트는 순공시간이 정상화 중이라는 거임
-
필요충분조건으로 바꿔서 플기에 대해 얘기하고싶다 항등식의 해석에 대해 얘기하고싶다...
-
기숙사 말고 자취 한다면 학비랑 돈이 많이 부담되는데 그래도 서울 갈 기회가 있다면...
-
Ps 고추장은 찾음 할머니가 직접 담그신거 있나 찾아본건데 그건 다 먹었더라고요...
-
맘스터치, 버거킹파라 맥날은 자주 안먹는데 뭐 먹을까
-
큰일났슴다.. 0
어제 통으로 쉬고 오늘.. 독서실 가야 하는데… 하.. 월요일날은 갔는데… 너무...
-
살'아야' 해서.....
-
10년뒤 한의대 VS 설공 전망은 ???
-
1과목은 사실상 확정 1과목은 고민
-
ㅆㅂ 다 그냥 다 해줬잖아 공부에 시간 좀 쓰라고
-
수학 실모 풀건데 추천해주세요
-
비상!! 12
비빔밥 해먹으려고 하는데 고추장을 못 찾겠음 부모님은 지금 외가에 계심
-
실검에 성욕이.. 뭐 중요하긴 하지..
-
다른건 다 모르겠고 학군지 + 남고 에서 왕따 당하는 애들은 진짜 매우 높은 확률로...
-
[단독] 돌솥비빔밥이 중국 지린성 문화유산? 3년 전 지정됐다 1
중국 정부가 중화민족 통합 정책을 강화하면서 김치나 한복, 태권도 등 한국...
-
이해원 n제 시즌1 보다 어려우려나
-
아 버스 놓친 2
바로 신호등 앞에서 놓쳤어 하 학원 가기 너무 귀찮다 누가 순간이동기 좀 만들어봐...
-
안지워져요?
-
진짜임. 진짜임.
-
천부적인 재능도 0
미친 하드워커 기질이 있는 것도 아니지만 걍 성실하게 까라면 까는거다 반은 가겠지
-
친구들 모여라 언제나 즐거워 뽀롱뽀롱뽀롱뽀롱뽀로로 뽀로로한 의대모험 출발~!!
-
[국어] : 박광일T 구주연마의 서 [1주차 미니모의고사 1회차] 맞힌 문제 :...
-
모때잡 2
모기때려잡는중..3마리 잡았는데 더 있을거란 불안감에 잠 못자기
-
Question: What best describes the narrator’s...
-
갓생 고고
-
서울가는중? 0
귀찮아유
-
더기나요??
-
얼버기 0
아까 낮에 자고 새벽에 자고 하루종일 잠만 자는 중
-
오운완 0
팔 힘이 세진 날 느껴 난 and i love it
-
올해 6모 92점 9모 100점 근데 이해원 s2 실모 풀어보니 0회 : 69 1회...
-
지역: 서울시, 과천시, 성남시 과목: 수학 (미적, 확통), 물리학1 - 2022...
-
일반과 수리논술 합격하신분 제발요ㅠㅠㅠㅠㅠㅠ 점수컷 어느정도 되어야...
-
엄밀히 말하면 틀린 정의를 옳은 잣대라고 믿고 타인에게 들이미는 인간들이 싫어요...
-
이런 유형은 어디서 구하나요..? 혹시 이렇게 공부해본 경험 있으신 분 구해요
-
let's go.
-
범위가 많아서 쉽게 내나 고2 9모는 등급컷이 거의 80 아님 84였는데 11모는...
-
수시충들 망해라 4
울학교(ㅈ반고) 메디컬 지망 수시충들 최저탈 기원 ㅋㅋㅋ 서울대 및 메디컬 쓰는...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.