컴공 일기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를 선물하세요.
-
어린이집 영유아니고 걍 abc 이런거 조금하는 걍 그런데 다니고 초딩때 학교에서...
-
영화 [기생충]에 나온 수험생이 가져야할 시험칠 때 태도 1
오늘은 다음 모의고사까지 하면 좋은 시험칠 때 태도에 대해서 소개해드리고자 글을...
-
9모 독서 블록체인 지문 수완 독서 ~교과서 재재 선정 강철중 모의고사 1회 강철중...
-
알람떠서 어디서 봤던거같은데.. 했는데 오르비 메인이었네 ㅋㅋ
-
자야지 18
-
싸그리 차단해버리게
-
보추는 예쁘다, 대우명제, 예쁘지않으면 보추가아니다 2
팩트포격
-
21회 개빡세네..
-
그러고보니까 보추말고 다들 보빔 한입 어떠세요
-
대체 어떤사람이 씌운 프레임임? 단어외워봤자 맨날 쳐까먹고 강의듣고 해석연습해봤자...
-
성공적으로 정착한 사람 김준 말고 또 있나요?
-
뭔가 수능날 잘 칠 거 같아서... 최저 맞출 수 있을 거 같다는 근거 없는...
-
자기장이 면적에 대해 평행하게 형성된거면 자기선속이 0인거죠????
-
이런 외모라서 추운데 살게된거아님? (어그로 ㅈㅅ)
-
인스타 들어가면 있는 유명 의대생들도 다 학교 안나가는 중인건가요? 와닿지가 않네 ㅋㅋ
-
메디키넷 아침 점심 먹고 있는데 저녁쯤 되니까 집중이 안 됨 남은 기간동안...
-
그렇지만 언어의 변화는 무쌍하기에 불규칙하게 변하는 것입니다. 그렇지만 이...
-
있어보이는 5성 호텔 막 신라호텔이나 시그니엘같은데서 와인먹어주면서.. 캬.. 늙어서도 멋있네요..
-
시발 근데 다 떠나서 워낙 지인 여부 떠나서 이딴 개저질급 범죄 계속 터지니까 나는...
-
내 인생의 원동력이 되어준 명대사
-
사문 선행연구 2
선행연구=문헌연구로봐도되는건가요?? 뭠차이죠
-
[자작] 접현각과 닮음 20
풀이랑 답 주시면 2000덕 드림 오류 발견하시면 1000덕 드림 히히히
-
이엑스아이는 5
코사인엑스플러스아이사인엑스
-
...저는 진실만을 말했습니다 어라라
-
사실 후회 안하고 다들 건강하게 수능 만점 맞을 예정임
-
오늘의 추천곡 16
오늘의 추천곡 원위- OFF ROAD, 유일한 사랑이니까 원위 다른 노래도 좋음...
-
이말에 반박하면 ㅂㅅ임
-
러 불규칙'이란 어미 '-어'가 '르'로 끝난 어간 뒤에서 '-러'로 바뀌는...
-
사문만 하면 자꾸 눈알이 삐는데
-
나도 빙고빙고 8
악귀네
-
보다는 옛날 애니들이 전 훨씬 좋음요...카우보이 비밥, 공각기동대, 에반게리온...
-
보ㅊ 빙고 무서운 점 16
Ver.2라고 적혀 있다
-
온몸 비틀기로 풀어서 겨우 80 나왔네
-
현역 공부 인증 7
어제 모고는 헬에 헬에 헬이였습니다..
-
복사에너지의 세기 관련 그래프가 플랑크 곡선이나 광도 나타낼 수 있는걸로 앎 근데...
-
더프야 빨리와라 0
내일 학교에서 풀어야한단 말이야
-
수능 악귀라 11
다행히도 1빙고
-
아배고파 0
끄흑
-
1. 전기음성도 계산할때 AB2라는게 있다고 해여 전기음성도 계산을 (A...
-
수학 실모 추천 받는다니까요
-
일반적인 유전알고리즘, 적합도 함수가 정해진 진화시뮬레이션이 아니라 신경망에...
-
다들 일여일에 7
긱사 다니는데 일요일에도 공부하는애들 보면 신기함 다들 일요일엔 공ㅂㅜ 얼마나하세요
-
보ㅊ 빙고 ㅇㅈ 18
살았다살았다살았다살았다살았다 그런데 화장품 기준이 뭔가요 토너 로션 선크림이 다긴 한데
-
3찍고 틀렸는데 3도 성립되지 않나... 가장 적절한건 아니라서 그런가 ㄱ이 분분한...
-
저 빙고 2
둘레 차이 20 이상 해당되는데 이거때문에 넣입못해요 님들은 복받은줄아십쇼
-
흡연자들 질문 12
공부하다가 담타가짐? 식후땡말고
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.