컴공 일기248
게시글 주소: https://m.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를 선물하세요.
-
이제야 현실을 알아차린 게 허수인데요.. 찍기특강은 어디서 들을 수 있나요? 알려주세요…
-
와 그럼 이제 07..? 이 곧 현역인 거야? 07은 너무 애긴데
-
고2 수학 7등급, 공부라는 건 어떻게 하는 걸까요 3
닉네임은 국잘수망이지만 정작 국어도 잘 못하는 이른바 노베이스 고등학교 2학년...
-
시즌4와서 극대 찍은 듯
-
기출을 아예 안 본 건 아니고 어려운 4점 몇 문항 빼곤 다 봄 현재 2등급 정도...
-
지금까지 사문 실모 한 30개 풀었고 보통 40점 초중반을 진동하는데..(가끔...
-
하면 공부안해도 씹존잘알파메일이 말걸어서 인생편해질수있나
-
형 내일 바탕 풀어야 한다.
-
다들 수능 힘내요 ((((큐브에 빡치는 일 있으면 중간에 들어올 수도...
-
작년에 웨이보 아칼리로 잡았는데
-
아름답다 5
후... 드가자
-
지지램쥐요 1
예압
-
취집마렵네 3
대학가서 경영대학생을 꼬실까 의대생을 꼬실까
-
아 그냥 한 과목 유기하고 싶다..
-
학과는 어떻게 1
정하셧나요 다들..딱 와닿는게 있으셨나요?? 딱히 간절하게 확고하게 하고싶은게...
-
제 1선택 이후에 2선택 응시할때요 2선택과목 마킹하다가 마킹 실수하면 omr용지를...
-
Oz랑 박선t 모고 난이도가 어떻게 될까용?
-
내신 기간 잠 5
내신이 빡센 학교라서 그런데 1달동안 하루에 커피 2잔 마시면서 3시간씩 자는거 어떤가요?
-
정말이지 유튜브보고싶다
-
솔랭임?
-
경제파트 관련해서 같은 주제를 상반된 관점으로 바라본 글 2개 골라서 수행해야하는데...
-
더 열심히 해야
-
입대 5개월 전 0
5개월 동안 수능 공부 고고혓
-
근데 진짜 2
왜 사탐안했지? 과탐은 그저 낭만인가
-
오르비에 고대냥 뱃지 올리기!
-
그건 내려가고 싶을 때 내려간다
-
22drx 23웨이보 24는..?
-
지들이 그리 욕하던 조센징이 만든 사이비랑 붙어먹다가 그거 들켜서 총선 나락ㅋㅋㅋㅋ...
-
흑흑
-
그냥…. 3
그냥 논술로 대학가면 좋겠다.. 수능 얼마 남지도 않고 하니 지금 하는 게 의미있나...
-
윤사 23
고정1 이신 분들 공뷰 뭐뭐하셧어요?
-
ㄹㅇ
-
하루에 총정리 2개씩해도 다 못함ㅋ
-
뭐이리 잘함?
-
16롤드컵 SKT T1대 락스 경기가 갑자기 생각남 4
그때 서폿미포 진짜 충격이였는데
-
라고 생각해보니 지난번 문학에서 개 말아먹었던게 생각이 난다 화작은 랜덤이고 문학을...
-
걍 아예 성별이랑 사/과탐 다 바뀌나? 진짜 모교가 젤 가깝긴한데 작년에도 좀...
-
수학 5->3 2
9모 52 맞았는데 남은 기간동안 열심히해서 3까지 가능할까요.. 낮3정도 지금...
-
비추??
-
어디임 님들은?
-
내년도 수능 보려고 해서 알아보다가 메가는 너무 비싸서 대성19패스 사전예약 했는데...
-
저격은 아닌데 5
수능앞두고 장문 사연 읽지마셈 솔직히 누구나 사연은 다 있고 읽는데 시간 아까워...
-
실모는 왤케 21을 어렵게 냄?
-
조때따 조때따 조때따 ㅋㅋ
-
킬캠 풀고 있는데 가끔은 등급컷 나오는 모고도 볼 필요가 있을 것 같아서요..!...
-
오르비 듣보 1인 수능 후에 돌아올게요(겁나 긴 장문주의) 5
이제 수능도 20일 안 남은 상황이고 밤중에 감성빨로 글 한 번 쓰고 싶기도...
-
ㅊㅊㅊㅊㅊㅊㅊㅊㅊㅊ좀 ㅊㅊ좀
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.