컴공 일기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
내신 20% 들어가는데 4점대면 어느정도 깍이는지 아시는분 있나요?
-
실패한 유전자 얘기 나오니까 자 여러분들이죠~ 실패한 유전자 이러는데 진짜 하나도...
-
덕코 받습니다 4
감사합니다.
-
올해 평가요소랑 면접여부 싹 바껴서 작년 등급컷이 의미있는지 잘 모르겠음..ㅠㅠ...
-
사실상 하나는 어디쓸지 확정이고 두개가 고민이네
-
승진쌤 개코 2회독끝내고 실코로 넘어가려했는데 작년에 기하 뉴런 수분감 사놓고 뉴런...
-
저는 그냥 수특만 무지성으로 푸는데 괜찮나요?
-
그냥 완전 혼자 지내도 아무 문제 안 생기겠죠?
-
수시6장평가좀 0
특목고 3.8 한양대 학종 추천 경영 경희대 학종 자전 중앙대 학종 부동산 시립대...
-
공통점은? 4
-
간짜장 2
숟가락으로가득퍼서양파까지우걱우걱
-
5.18 희생자들의 존엄을 부정하는 거임? ㅋㅋ 존나 웃기노
-
언매 1
여러분들 6모 9모 시간 얼마나 걸리셨나요? 그리구 국어에서 이상적 시간배분은...
-
내츄럴 본 극외향인 인싸 존잘 존예 enfp esfp 들이 저보고 왜 MT 안...
-
좋아요 시 1만덕 드림 17
사실 엄청 좋은 자료기도 하고 예전에 저분께 도움받은 것도 있어서 글을 씁니다....
-
평소에 그냥 시간 조금씩 남기고 교육청 90점대 평가원은 중간2등급정도 나오는편...
-
맘에 안들면 떨구지 않나
-
연대학추레전드노 0
ㅈㄴ다터짐 연대학추 쓰신분?ㅜㅜ
-
와 통계역학 0
앙상블 배우는데 어렵네...근데 좀 재밌음
-
경쟁률 개빡세다 징말....ㅠㅡㅠ
-
수시 카드 성대 0
성대 건축(5년제) vs 건설환경공학부 학종 수시카드로 뭐가 나을까요?? 성대는...
-
수리논술만 쓸께요 접수전에 이런글 쓰면 선동한다고해서 끝나고 써용 '논술'은 실력에...
-
인문논술 과외경험없는 선생님한테 맡기는거 오반가요? 0
최저는 맞출 자신이 있어서 성균관대 중앙대 위주로 준비하려고 하는데 24학번으로...
-
막막하네요
-
그다음에 기억나는 게 물1시험지 붙잡고 이미 정신 가출한 나...
-
국어 수학중에
-
수시반수로 0
성신여대 공대 ->아주대 보안 쓰는거 의미 있나?
-
왜 수위가 높아졌냐.. 13
-
어차피 풀면서 느낌이 옴 그러니까 빠르게 던질 문제들 던져야 함
-
걍 한단원에 3점부터 킬러까지 다 있는 게 좋음 강사기출은 스텝 다 쪼개놔서 풀기 불편하던데 ㅋㅋ
-
안녕하세요 17학번머스크입니다 [이감수학 파이널 플러스 모의고사] 미쳐서 안팔고 뿌립니다. 많관부
-
이..이게 아니고 이겁니당 9평 그런건 아무것도 아니야! 두 달이면 충분해요!!...
-
그냥 원래도 어울리기 싫은 사람이 삼수를 했을뿐
-
이중도플러 0
-
언 77 69 61 51 화 80 72 64 55 미적 76 68 60 51 기하...
-
토요일에 서바수업->강k수업인데 보통 2단과 하면 중간에 카페인 드심??????...
-
나는 “이타적인 행동의 본질은 이기적이다“라는 생각을 항상 하던 사람이었다...
-
ㅈㄱㄴ임 고논 8시반 서강대 2시 가능?
-
사문 개념 수특 0
수특 10강 짜리 강의 있던데 그걸로 충분할까요??
-
대학 수시 0
지방 사립대인데 지역인재 전형에서 10명 모집에 아직까지는 7명밖에 지원을 안 한...
-
이런 글에 무조건 가능하다고 해줘야 하는 이유 안 된다고 하면 뭐 어쩔거임? 안...
-
단국대 쓰려했는데 친구들이 서울에서 죽전으로 본캠 옮겼다고 이제 하락세라고 그러는데...
-
현역이고 생기부는 의대랑 공학 연구 쪽으로 되어있어요. 의대 지역인재 4장 서울대...
-
하 6광탈 각인데 어떡하지 싶으면 걸려들어오는 매직
-
수특 0
아직 올해 수특 수완 한번도 안봤는데 국어 수특 수완 공부하면 시간 단축 효과...
-
고대는 걍 질렀으니까 빼고 스이서성한은 애초에 못가고 중경은 쓸 만한 과가 없고...
-
누구링 사귀든 애칭 동일함? 바뀜?
-
지교썼는데 실질경쟁률 얼마나 되려나
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.