컴공 일기248
게시글 주소: https://old.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를 선물하세요.
-
이런 글에 무조건 가능하다고 해줘야 하는 이유 안 된다고 하면 뭐 어쩔거임? 안...
-
단국대 쓰려했는데 친구들이 서울에서 죽전으로 본캠 옮겼다고 이제 하락세라고 그러는데...
-
현역이고 생기부는 의대랑 공학 연구 쪽으로 되어있어요. 의대 지역인재 4장 서울대...
-
하 6광탈 각인데 어떡하지 싶으면 걸려들어오는 매직
-
수특 0
아직 올해 수특 수완 한번도 안봤는데 국어 수특 수완 공부하면 시간 단축 효과...
-
고대는 걍 질렀으니까 빼고 스이서성한은 애초에 못가고 중경은 쓸 만한 과가 없고...
-
누구링 사귀든 애칭 동일함? 바뀜?
-
지교썼는데 실질경쟁률 얼마나 되려나
-
암것도 안하다가 오능 밤에 할 생각인데 증명사진도 ㄴ없고 시간표도 다시 다 알아봐야...
-
틀딲이라고 같이 안 놀아주는 거 아닌가요? 걱정되네요
-
제노 챌린지샤프 << 바뀐다는 소문이 있음 유미 미래샤프 << 여태 있었던거 둘다...
-
답례품으로 기차 기다리는 동안 카페에서 아이패드로 원하는 어구 적어줌(악필임)
-
화작, 확통, 생윤, 사문 순서 6모 43412 9모 33411 국어는 3후~4초...
-
어디 남았죠 서성한도 요번주 끝이고
-
조언임.
-
일단 수시로 붙은 대학 걸어놓고 군휴학 하고 공군가서 21개월 동안 평일에 5시간...
-
"응급실 못 가? 어쩌라고" 의대생들만의 '기괴한' 우월감 [Y녹취록] 2
■ 진행 : 윤재희 앵커 ■ 출연 : 오윤성 순천향대 경찰행정학과 교수 * 아래...
-
엥??
-
6광탈 준비완료
-
기분이 오묘하구먼
-
8회차 41점 ㅜㅜ 복습 빡세게 해서 고정 45이상으로 올려야지
-
물론 5만덕 줄 사람이 없을거 같음 연머 마감 30분전이다 이거 지금 기억났으면...
-
건대 과 추천 3
수시 원서 쓰기전 경제vs부동산 어디가 좋고 유망할까요?? 주식투자랑 경제...
-
이거 졸업했으면 3학년으로 체크하면 되는건가요 ㅠㅠ?
-
를! 던지고 국어를 해라.
-
기출이랑 연계 계속 돌려야하나
-
원조 방법은 보니까 등쪽 자극될만한게 없어보여서 턱걸이 넣어보긴했는데 어떤거같음요?...
-
수학 1진짜 0
갈기갈기 찢어서 패죽이고싶다
-
이렇게계산많아도돼?
-
젖지대머리 8
젖지대머리
-
연논 무슨과 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% 적중 문제 나왔다구?” 컨스텔라 모의고사 무료 배포★ 0
안녕하세요.오르비 X 매시브 강원우 연구실 입니다. 이번 9평 보느라 고생한 올비...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.