컴공 일기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를 선물하세요.
-
멀리보면 맞는게 나을거 같은데 주사 맞르면 하루이틀정도 컨디션 이슈가 생길거같은데...
-
화학 vs 지구 1
7월에 물리를 지구로 바꾼 반수생입니다. 9모등급은 원점수 기준 각각 40,...
-
사문 1등급 표점이랑 과탐 가산점 3%, 5%일때 몇등급과 표점이 비슷한가요??
-
100넘긴데가 안보이네 99.8이라지만 연치 연약도 100안넘겼고아직 생각보다...
-
메가 9평 라이브 이벤트 같은거 당첨자가 있긴 함? 공지도 안뜨는데 0
항상 궁금해서 이번에 9평 댓글이벤트 어제 당첨자 올라온다길래 계속 공지사항 당첨자...
-
수학 5등급임 18
학교수업 외에 공부는 한적 없고 2달동안 딱 3등급만 만들면 좋겠는데, 뭘 해야...
-
글리젠 뭐뇨이… 왜케 빠르냐뇨이…
-
보면 볼수록 내신 좀 딸려서 못갈것같은데 인문계열로 틀어야할까요ㅠ 작년거 보니 70퍼컷도 못들던데
-
아주대 논술 0
기계공학과 5명뽑고 자전 10명 뽑는데 경쟁률 비슷하면 자전으로 하는게 낫나요?...
-
온 세상이 봇치라는 명확한 증거다
-
킬캠 2
내가 킬캠을 72점을 넘다니
-
이미지 n티켓 1
시즌1,2 난도 다름?
-
너구리 사왔다 20
다시마랑 건더기 쳐내고 치즈랑 계란을 샤악
-
간쓸개 개빡치네 6
진지하게 문제퀄은 수특이 더 좋은듯
-
현역 정시파이터고 학교가 어수선해서 선생님께 몸 안좋아서 조퇴한다고 햇는데 자기는...
-
천코만 주세요 2
감가상각하빈다
-
나중 3년내에 반도체쪽 연구소 생겨서 아웃풋 좋아보이는데 어떻게 생각하시나요?...
-
공대 목표 사탐런 하려는데 문과로 많이 트나요…? 그냥 이과로 계속 가려고 하는데….
-
입시 일정 고려하며 수험생 신경쓸 대단한 세심함이라면 교육여건 고려하고 2000명...
-
이런거보면 진짜 고시는 사람 할게 못되는듯 ㄹㅇ 1차 한 1년 정도 걸렸다 쳐도...
-
ㅈ댓다 파일 없는대 어캄?
-
그러니까 이게 스엠이 공인한 스엠상의 정석이라는 거군
-
오늘 컨디션 미친놈이여서 실모 풀세트돌리려했는데 이게 뭔 대재앙이냐..
-
국어 100점 그 이상 12
-
시립대워떡하지 0
시립대 서류형 면접형 고민중인데 면접형이면 사회복지로 내서 등급컷이나 생기부...
-
시즌마다 상이하다는데 그냥 전체적으로 봤을때 풀만할까요? 지금 높2-낮1정도고 이...
-
수능 최저 미충족 지원자는 제외하고 합격자 발표가 나오나요? 합격자 발표일이 수능...
-
수능은 스쿠나다 0
수험생에게 세계참을 날리는
-
수시로 국숭세단 갈 고3인데 내년부터 바로 군수 박을 예정입니다. 중경외시부터...
-
평가원, 수능, 교육청 지문하고 국어 주간지 지문하고 무엇인지는 모르겠지만 이질감이...
-
작수때 145받으셨던 분의 길을 따라가본다
-
옳지 않은 것을 골라야하고 답은 2번이에요. 1,2번 선지가 궁금해요 읽어주셔서 감사합니다
-
라고 모솔찐따가
-
성대 논술 지원합니다 성대는 탐구끼리 합칠수가 있어서 사탐충인 저한테 유리한 것...
-
2024 수분감이랑 2025 수분감이랑 많이 다른가요? 4
2024 수분감이 엄청 싸게 올라와서 중고로 샀는데 2025 수분감 강의랑 많이 다른가요?
-
패논패 자휴때릴까
-
문과 취업은 9
학과 살려서 가는것보다 그냥 따로 시험 준비하는 사람이 더 많다던대 사실인가요?
-
어느게 더 충족률이 높나요?
-
독서 -4 문학 -5 언매 -5 해서 86점 1컷 86점인데 1컷 너무 높게 잡힌거 아닌가요..?
-
지구1 11월 수능전까지 공부 질문있습니다!! ㅜㅜ 10
지금 오지훈 선생님 커리 유자분까지 완강한 상태이고 스텝4문제는 이제...
-
입도 잘 안 벌어지고 귀랑 턱 다 아픈데 ㅠㅠ 큰 병이면 어캄 .. 개무섭네...
-
6모 9모 작품 연계 적중된 회차 있을까요? 그거 빼고 풀려구요 ㅠㅠ
-
재수생입니다 작수 경희대 공대 올해 6모 인설약 9모 고대 공대 성적입니다 수학은...
-
정시합격 예측 0
어디가 젤 정확하나요?
-
2합5인데 사탐허용 실질은과연?
-
내가 뭘 잘못 보는 건가 어제 마감 아님?
-
제발 어렵다고 해줘…
-
컴공 쓸려고 하는데 작년보다 이미 지원자수 넘어섰고… IT융합이나 지능형반도체...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.