컴공 일기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를 선물하세요.
-
사범대 지원했는데 ㄷㄱㄷㄱ ㅋㅋ
-
사설이라 그렇다고 해줘요 제발 좆같이 안풀리네
-
[Zola] 이거 국어로 풀리지 않나요??(개념 말고 국어!) 6
생윤 강사인데....국어에 글 올려서 죄송요... 을 : 우리는 자신을 위해...
-
중간에 뭔가 다른 분 껴있다고해도 넘어가라게슝
-
1.작년엔 자연과학이 오전 공학이 오후였던것같은데 올해는 바뀐건가요?? 2....
-
아니 6
다들 경희대 메디컬 과학논술 보는 거 알고 지원하는 건가? 왜이리 많지 ㄷㄷ 글 쓴...
-
총과제에서 말고 선생님께서 직접 소재를 다뤄주시진 않죠? 작년에 들었는데 기억이...
-
ㅈㄱㄴ 인문논술이라도 쓸려하는데 수능 후에 있는 최저빡센 인문논술 뮤ㅓ가있을까여
-
자기 “수학 5에서 1로 올렸어요!” 이런 글 보면 21
5등급 실력이 정말정말 죽을듯이 노력해서 1로 올린거처럼 말하길래 그런 드라마틱한...
-
경쟁률이 애매해서 모르겠음
-
미디어 이번에 왤케 낮아.. 하..미디어넣을걸그랬나
-
지방 일반고 현재 2학년이고 지금까지 1.19인데 전기정보가 농어촌 컷이...
-
수학푸는데 생각보다 너무 많다... 중간중간에 어? 싶은 연계가 괸 문제도 있고...
-
수시원서접수 결제까지 다했는데 보니깐 마감시간으로 부터 몇초 초과됬던데...
-
고대논술 미디어 2
최저 많이 맞출까요? 미디어 과 특성상 매니아층 많은건 아는데 그만큼 과 이름만...
-
반수생입니다 9모 가채점 기준 언미영화1생1 95 96 90 47 47 이라 둘 다...
-
원서 한장이 남아서 고민중인데 문과생이 어디로 가는게 더 나을까요..?
-
그말이옳을까tv 1
안녕하세요 망해tv의 그말이옳을까입니다.
-
생1 1년반동안 하면서 한번도 들어본적이 없는데 오늘 n제 풀다가 갑자기 튀어나와서 당황함
-
생윤 질문 2
칸트의 입장에서 ㄷ선지는 왜 아닌지 모르겠어요. 테일러는 생명체 중심주의니까...
-
여기저기에서 0
반수얘기가 나오는구나...
-
5년전쯤엔 엄청 높았던거같은데 입결표보니까 저밑에있네요
-
9모 45점인데 뭐 해야할지 모루게씀
-
3분의 1정도 나간거려나요? 적분 난이도도 고려하면 4분의 1밖에 안되려나;
-
서울대 지균 6
서울대 첨단융합학부 지균전형으로 러제 지원했어요. 경쟁률 5대 1 빡세네요......
-
돌았나미친새끼가
-
상상도 못했네 경제도 이제 메이저과목!?
-
3만대 나올 각오 하고 있었는데 저러면 실제 수능도 응시자 4만은 나오겠네
-
여기서 전투휴무 5일에 말출 아낀 휴가 30일 있음 어떰???? 전투휴무 정의...
-
수시입양기원 1일차
-
강아지 4
침대랑 제 옆에 낑겨서 자고잇네요 귀여브라
-
오래전 일이긴한데 경대 시험보고 1차 떨어져서 멘탈 가루 됐을 때 독서실 가서 이게...
-
9모 이후 영어 공부계획 조언부탁드립니다! 꼭 봐주세요.. 3
무조건 영어로 논술 최저 2합5 맞춰야하는 수시러입니다 메인은 영어 수학인데 혹시...
-
학종은 뭐 예측하는게 의미없긴한데 교과는 전체 지원 집단의 대충 어느정도가 낙지...
-
화2 기출 3
경향성이 예전 거 볼수록 너무 달라지는 거 같은데ㅜㅜ 실수분들...몇개년 추천하시나요
-
글경제가 선호도가 낮나요? 경쟁률이 꽤 유의미하게 차이나는데.. 아니면 마지막 날...
-
2등급 목푠데 추론형 너무 딸려서 1달동안 18모고랑 같이 돌릴건데 상크스랑...
-
과탐 특히 ㅅㅂ
-
1-2 왔다갔다함
-
제곧내입니다
-
이번 의대 증원 논란 첨부터 궁금했던건데 그냥 의사들이 돌아오면 해결되는거 아님?...
-
근거도 같이 주시면 아주 감사링
-
공대지망인데, 설공이나 고공이나 크게 차이날것 같지는 않아서 그냥 고대 두장썼어요.
-
기후 변화와 지구 온난화
-
논술에 형도 참전이야 어어 붙지안붙을지는모르겠는데 일단 그때 심심하니까 지를게?
-
빨리 국어실모랑 언매 벅벅하고 9시쯤 학원에서 나와야겠어요
-
학추 불이익 2
제가 학추 신청을 했는데 그 학교에 학추(교과)로 말고 학종으로 넣고 싶어요......
-
https://orbi.kr/profile/1337129...
-
이게 뭐람 ㅋㅋ
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.