컴공 일기248
게시글 주소: https://iu.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를 선물하세요.
-
한시간동안 저거 세문제 푸니까 정신나갈거같은데 (심지어 첫번째꺼는 풀지도 못함)...
-
대성패스밖에 없어서 생1 내신대비로 대성이나 EBS중에 하나 들어야할것같은데 괜찮은...
-
국어 실모 질문 0
상상이나 한수 off 비재원생한테 파는 학원(대치) 아시는분 계신가요? +) 서비나...
-
왜지
-
지금 집가는게 맞냐
-
뇌가 과부화 해서 그런지 글이 잘 않읽힘 이건 실모 많이 풀면 해결될까요? 수학은 안그럼….
-
메렁 3
-
지인선 1회 2
통통이 6평 백분위61.. 지인선 1회 60분 2틀 나왔는데 계속 풀어도 되나요?...
-
이미 시스템 강좌에서 기출 같이 해주는데 따로필요한가요? 아님 큐뱅크로도 충분할까요
-
사문 생윤황들 1
공부 뭐하심 요즘 사탐런했는데 뭔가뭔가임…0
-
틀린 수학문제 오답할때 강의 안듣고 해설지만 보고 오답하면 0
효율 떨어질까요?? 메가 수학 컨텐츠 풀고싶은데 메가패스눈 없어서요ㅠㅠ
-
뭔가 기분이 6
삐지고 싶음!
-
재작년에는 없었던거로 기억하거든요 작년에도 없었음?
-
장클+파이널 클래스 기출의미래 독서문학화작 수특수완연계
-
암거나 추천좀 스포츠물만 봤었음
-
공통 베이스가 잇어서 계속 2등급뜨고있긴한데 미적 27부터 주르륵 틀립니다.....
-
ㅈㄱㄴ 풀어보신분들 정보좀..
-
역대급 폭락 쳐맞고 연달아서 달러 평가절하까지 쳐맞네 5
미주 하기 참힘들다... 그렇다고 국장으로 다시 돌아올 생각은 없지만
-
요즘 다시 개학해서 학교 다니고 있는데 일방적인 기싸움 때문에 정말 스트레스...
-
기분이가 좋네요 ㅎㅎ
-
문제 진짜 좋아용 드릴보다 약간?? 더 어려워요 설맞이 하기전에 빨리 쳐내려고...
-
대충 수능, 입시 정보 주고받는 건전한 커뮤인줄 알았는디 오늘 보니 아닌거...
-
안녕하세요. 수학 공부 관련해서 질문드립니다!! 현재 어삼쉬사 수1 수2 확통중인데...
-
국어 기출 16~24년까지 1회독만 진행했습니다 1회독은 마닳 1부(20...
-
엔제 뭐풀죠 0
4점코드 시즌 1,2 -> 4규 푸는중인데 4규 풀고나면 뭐풀까여 빅포텐 s1,...
-
행복해요
-
SKY반이었잖아 우리때는
-
ㅇㅇ,,,,
-
고사장이 이상한 곳으로 가나요? 멀리떨어지고 그런가
-
강기분 새기분 독서 문학 다 끝냈는데 이제 뭐해야할까요?.. (Ebs 안해서 일단...
-
오늘 퀄s2회랑 서바4회쳣는데 둘다88인데 컷이보통어떻게나옴?
-
진짜 농담이 아니라 사설 풀면 매체 주룩주룩 틀리는데 해결책 잇음요?? 원래 매체는...
-
사이트에 수1만 나와있던데 미적은 아직 안 나온건가요?
-
20분박고못푼사람을뭐라고함아.30풀껄그랬나양모 22 30 진짜 개매움
-
대충살자 0
딸 생일파티에서 딸로 피냐타 깨뜨리는 칸예마냥
-
이중적분이랑 삼중적분... ¡HIJUEPUTAAAAAA!
-
지금 부터 수학 영어 지구만 파서 7모 34246 로 수학 포함 2합 5 가능?? ㅠㅜ
-
제가 영어 인강을 들어보려 하는데 아예 인강이 처음입니다. 오르비에 글 쓰는 것도...
-
내신이랑 생기부 평가 좀 해주세요…학종 가능성 있나요 ㅠㅜ 8
성적은 1학년 1학기 부터 순서대로고 마지막 사진은 3학년 자율 진로랑 미적분 기하...
-
교육과정 성취기준까지 적었습니다~ 초등 의대반 열수 있을까요?
-
독서보다 문학이 어려운편 문학작품 해석이 잘 안되고(시같은거 읽으면 뭐라는지...
-
강x 1
9모 끝나도 풀려고 하는데 그때도 시즌1,2 해설강의 벌 수 있나요? 해설은 걍...
-
22 30틀 22에ㅜ모든걸걸엇는ㄷ시발시발세발......못풂.....으ㅢ시발
-
아직 우리나라에 현역때 화염병 제조 뛰신 전문가들이 눈 시퍼렇게 뜨고 살아있다는걸 간과하신듯
-
충분하게 해결을 못해서 재업합니다.. 2주 동안 공부량이나 방향 어떤지 조언...
-
수능 십새
-
'연직자기력/수평자기력' =tan(복각) 으로 처리하면 빠릿빠릿하게 선지 판단 ㄱㄴ...
-
8/20 일기 4
공부시간과 별개로 공부량자체는 많지않아 아쉬움이 남는하루. 특히 오전~1시경까지...
-
역시 사탐런은 0
내 성적대는 다시 생각해보는게 맞는듯하다.. 지금돌렸다가 1등급못띄우면 진짜 답이...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??