컴공 일기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를 선물하세요.
-
이제부터 실모 병행하려하는데 국어 실모 이감 ㄱㅊ? 0
이감 어디서 부터 해야하나요?? 실모는 첨이라서 ㅜ
-
방빼!!ㅔ
-
히카랑 서바 0
서바 80초 나오는데 히카 모의고사 풀어서 96 나왔어요. 히카가 많이 쉽고 서바가 어려운거죠??
-
틀니 빼버리고싶네 저새끼들땜에 글리젠 ㅈ망한거도있는데
-
MC 무 4
-
뭘
-
[수학] 높은 실모 난이도에 지칠 때 feat. 홍보 2
안녕하세요 수학강사 이대은입니다. 오늘은 강의홍보를 위해 왔습니다! 수능이 40일...
-
인증) 12
스벅 아이스블랙글레이즈드라떼
-
언어: 142 수리: 86 이래서 내가 예체능인가봐
-
전역 D-3 14
총기반납까지 완료 이제 진짜 좀 가고 싶다
-
나도국어의신
-
독서 -5 문학 -4 언매 -2 89 으어어어 이정도면 수능이었으면 1컷이었을라나,,,
-
존나게 익숙하지않구나 매우 불편
-
사설(이감 상상 더프 등)에서 생명 지문, 특히 질병 관련 지문에서 비타민 K 식...
-
반수 같이 하던 여자친구랑 오늘 내 생일에 헤어졌다..생일에 재수학원 가는 것도...
-
그냥 갑자기 여기선 안되겠지?
-
작수 6등급이었던 예체능 친구가 본인피셜 현재 사설 모고풀면 80점대 후반에서...
-
관통해드림
-
ㅇㅇ
-
극락..
-
그거 과마다 문제 가중치 조금씩 다르지않냐고 물었는데 ??ㄹㅇ ? ㅇㅈㄹ하고...
-
미적이라 모르는데 통통이 친구들 피셜로는 확통 어렵게 내면 어차피 안 풀어서...
-
수도권 1호선 역세권인데 농어촌+지역인재가 가능한 동네.... 3
바로 ”충남 아산시 탕정면“ 읍도 아니고 “면” 수도권 전철 1호선 역세권 KTX...
-
이감 6-1 1
9모보다는 어려웠는데 똑같이 93점 뜸 발전... 하고 있는건가 3등급 탈출시급
-
댓 ㄱㄱ
-
27수능까지 꽉꽉채워서 보면 갈 수 있을까
-
나랑 나이 비슷할텐데 ㅈㄴ 잘하는거 보면 ㅈㄴ 현타옴 이거 어케 극복하누
-
점메추 ㄱㄱ
-
성지글 1
현역 언미영생지 44234 재수 언미영생지 13222 삼수 언미영생지 12121
-
레전드삽질 4
잘 풀고 잇엇는데 그래프만 쳐다보다 보니까 주기를 대칭성으로 잘못 봐갖고 12 13...
-
뒤늦은 9모 인증) 13
망했어요
-
고액과외 같은거 받았을 때 성적이 올랐다-> 다른 수업 들었어도 올랐을 녀석이다...
-
실제로 인플루언서들 많이 봤는데 실제로는 몸 안 좋은 건 고사하고 얼굴까지 축 쳐진 경우도 많더라
-
국어실모에서 턱걸이 1도 아니고 안정적으로 1 떳음 ㅠ 진심 감격스러워서 눈물은...
-
진짜 어려운 지문을 읽을 때 문장마다 자신의 언어로 정리하는 동시에 내가 읽고 있는...
-
언미영생지 기준
-
ㅈㄴ 슬프다 공부 잘하고 싶다 수능잘보고 싶다
-
일단 화작&독서론 -> 가나지문 -> 문학 -> 나머지 독서 두지문이렇게 풀고 보통...
-
자습중에 에어팟 껴도 되나요 노래 듣는 목적으로요 그리고 현강 꼭 매일 3시간씩 다...
-
제 생각은 그렇네요 그 어떤 분야보다 이공계적이면서, 그 어떤 이공계보다...
-
날 더 강하게 만들뿐 밤 새고 똥참으면서 이감 6-4
-
정답률 75프로 미만의 사설 문제는 사설이 사설한거므로 맞은걸로 채크한다. 이감 98흭득 완료
-
바탕 7회 후기 0
언매 2틀 공통 3틀 88점 틀린 문제 해설보면 충분히 납득이 가서 좋은 모의고사같아요
-
디디라는 사람은 납치,공갈,인신매매,살인 혐의로 체포됐다고 함 단순 음모론일지...
-
없다 얻다는 최소 대립쌍이죠?? 발음으로 비교하니까 자음군 단순화 후 된소리화 돼서...
-
사람 한명 살린다 생각하고 지적 좀 부탁 허수담요단 나인거 같음 필기 너무 열심히함
-
6모때 승강심사로 올키 장학 받고있었는데 9모 올키 유지하려면 마찬가지로 국수탐 올...
-
내 공부 장점 2
1) 글을 잘 쓴다 2) 꼼꼼하다 3) 정리를 잘한다 4) 예습복습을 잘한다...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.