컴공 일기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를 선물하세요.
-
연논 무슨과 5
인문애들이 글쓰기를 잘한다는 말이 타당할까요?
-
고논 하나 2
오직 그 뿐
-
그불구 더데유데 컬미네이션 아니면 션티 키센스까지 4개중에 하나 할 생각입니다...
-
노트쉘프 3 0
필기감 좋다
-
경쟁률 질문좀 5
담임쌤이 경쟁률 12대 1에 가까운 곳에 넣으라는데 이유가 뭔지.... 고민하는...
-
민초 vs 맥콜
-
돈 좋아~
-
Zola임당 인강 겸 현강 겸 추석 특강 소개 겸 9평 킬러 선지 확인용 글입니다....
-
수능전까진 논술공부 안 할거고 수시 안 쓰기는 좀 그래서 몇장 쓰려는데...
-
대부분 낮은 대학교거나(성적대가) 아니면 서해5도 장애인전형같은 특수한 전형을 써야...
-
개비쌈
-
아 3점 틀림 7
치환적분하다가 2어디로 날려먹었냐 ㅋㅋ
-
다른 곳도 아니고 ebs에서 나온게 있었음
-
몬스터 한 캔 마시려는데 단백질음료랑 순간 착각해서 흔들고 캔을 따버림
-
더 많이 감소한다는 게 감소량이 크다는 거지 감소율이 크다는 의미가 아니지 않음?...
-
무슨 어디 불교용어같네 나무아미타불 관셈보살 언기화투경
-
( 강원대병원 의사들 " 증원 아닌 필수 의료 문제 해결해야 " ) 0
https://www.yna.co.kr/view/AKR20240912130800062
-
[★앵콜 이벤트] “9평 영어 점수 1등급? 여기서 100% 적중 문제 나왔다구?” 컨스텔라 모의고사 무료 배포 2
안녕하세요.오르비 X 매시브 강원우 연구실 입니다. 이번 9평 보느라 고생한 올비...
-
2컷이라면 백분위 95인건가요 백분위 89인건가요?
-
내 원서가 지금 총 내신 2.2에 3-1에 1.17 찍은 상승곡선에다가 생기부...
-
재수까진ok 삼수 이상부터 문젠건가..?
-
외대 넣을거면 경영 넣을듯해요 외대는 지금 기준 31명 뽑는데 1262명...
-
학교쌤들이 정시도 생기부 보는곳들 있다, 생기부 없이 수능성적만으로는 한계가...
-
문관데 너무 의견이 갈려서요… 어디 쓸까요……
-
13일까지 접수할 수 있는 걸로 아는데 사실상 정시에 올인이라 논술은 그냥...
-
제가 어려서 잘 몰라서 그러는데 3수 4수씩하면 손해보는 것이 있나요? 예를 들어...
-
영어 국어 학생 과외 알아보려는데
-
3일동안 핫식스 하루 2캔 퍼마시니 너무 피곤하다 10
1캔으로 줄여야지
-
연논 0
화공 22 신소재 27 시반 27 인데 충원율 높은 신소재 넣는게 정배인가요??
-
원서 쓸 때 '논술전형 지원자격' 란에 동그라미 되어있는거 체크 안되는 거죠?...
-
화공은 이름과 달리 물리가 주 라는건 알고있는데 화학도 마찬가지인가요?
-
과탐 선택 고민 1
07년생이고 화학이 넘 좋아서 화1화2 볼려고 했는데 이번 9모보니 표본이 너무...
-
를 정리해두신 분이 계시네요. 아래 링크는 그분 프로필입니다....
-
https://m.dcinside.com/board/airsoftgun/352291?...
-
공부하기 시러 3
그래서 안하는중
-
인논이랑 수논을 어떻게 백분위로 하는거지…
-
두 학교만 넣었는데도 13만원이 날라갔어요 세 개 더 넣어야하는데..ㅎ
-
현실은 4등급
-
흐어어엉
-
마음에 들지 않는 자기소개서 문항 사람의 기질은 환경에 따라 나타나는 방식이 변한다...
-
3년 내내 변한 적 없었음 ㅠ 인하 순천향아 나 좀 보내주라… 나 선출이라 체력 짱 좋은데 ㅠㅠ
-
쓸까요 학교는 성대가 더 좋은데 유형이 더 어려워서
-
그이상 난이도는 하다가 탈모올 거 같다 난 역시 물스퍼거가 아니라서 깨끗해
-
한국사 인강 0
한국사 1번문제밖에 못푸는 매국노인데 권용기 인강 중에 컴팩트 퍼팩트 중에 뭐 들어야하나요
-
시선이 어떨까요 현역 수시 국숭세단에서 시작해서 3수 중경외시 경영 간다 치면...
-
뭐를 더 좋게 봄? 국어 수학임
-
어떡하죠.. 잠 줄이는 법이나 안 피곤해지는 법 좀 알랴주세요ㅜㅜ 비타민b 먹었는데도 이럼..
-
대학수학능력시험을 주관하는 한국교육과정평가원이 오늘자 수능 채점 결과를 발표하며...
-
어느정도 급간으로 올라가는게 정배임? 지방의?
-
알았는데 어지럽고 림프절 붓고 그럴 수 있다네.. 아… 외이도염이래요 ㅠㅡㅠ
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.