컴공 일기248
게시글 주소: https://a.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를 선물하세요.
-
??
-
아오씨 ㅋㅋㅋ 힘들어 죽겠네 어사대 비서성.
-
그래서 점심 저녁 시간엔 공부 안하고 걍 엄선경쌤 ebs연계만 들음..
-
가형 시절 1받고 논술 몰빵했는데 연논 예비로 떨어지고 N수 스타트
-
그렇게 잘하는 건 아니었지만 그래도 나름 현역 때 1년 내내 적어도 1등급은 받던...
-
고대논술 시간 3
자연계열 오전타임 오후타임 있던데 각각 하나씩 써도 상관없는건가요?
-
성대 공학계열이랑 전전 논술 컷보니까 2점차이나던데 이정도면 유의미한 점수인가요?...
-
1컷 몇 예상하시나요
-
안녕하세요, Uni-K LAB 입니다 메디컬 논술을 노리는, 화학1을 경험해본...
-
과탐11이 압도적으로 어려운가
-
연세 반도체 성대 반도체 원세 의예 3논술 let's go
-
과탐1과목 사탐1과목인데 사탐1과목빼고 나머지 4개로 최저맞출수있나요 ?
-
1아니면 3이었기에
-
궁금합니다요...
-
난이도도 적당히 있고 문제 퀄도 좋고 무엇보다 내 수준에 너무 어려운 모고는 못풀어서 딱 맞음
-
이전부터 궁금했음
-
수학은 죽었다 깨도 3은 안나오는데 국어는 툭 하면 3나옴
-
와 난생 처음보는 점수 받아봐서 너무 당황스럽네요 그래도 69모 1등급...
-
의대 증원 + 영재고 의대 학종 지원 불가능 첫 해 후 정시만 올해 역대급 피터지겠네
-
다 늘어짐 걍 학교 가서 꾸득꾸득 자습하는 게 훨 나음
-
문학 연계작품 웹툰으로 보는 국밥이라는 앱인데, 이용권 비싸서 1/N 하려고...
-
갑자기 미디어콘텐츠학과에 관심이 생겼다. 내 적성에 맞는 학과 진짜 찾기 힘든데...
-
강대x 풀면 84~88 진동하는데 수능때 백분위 98가능인가..
-
국어 빼고 다 12고 군대 가서 수능 볼 건데 평가원 기출 솔직히 어느정도 기억...
-
수학 ㅈ된건가 0
기출에 나오는 수능틱한 문젠 익숙해서 ㄱㅊ은데 시중문제집, 내신틱한 문제..같은건...
-
닭강정먹고싶다 1
ㄹㅇ
-
마더텅말공
-
원래 첫해는 꿀이라고했어
-
언미영정법사문 6모 21213 / 9모 32113 6모랑 9모 성적차이가 커서...
-
원서접수 했는데 이제 당일날 수험표 뽑아서 가면 끝이죠? 없는 거 같은데 불안해서 물어봄
-
내일부터 나는 다시 정시파이터다... 화이팅!!!
-
심 듣다가 김동욱쌤 파이널로 장클 들을려고하는데 ㄱㅊ? 5
김동욱쌤 스타일 아예 모르는데 중간에 들어가서 적응 가능한가.... 이번 9평은...
-
수능 정점 찍었던 , 괴수들 수능다시보면 우리 ㅈ되는거아님, , , ???...
-
논술 질문 0
6,9평 수학 1컷인데 추천하는 논술 학교 있을까요? 수능 전에 논술 공부를 많이...
-
독재중인데요, 이감 하반기 실모 구매해서 풀어볼까 고민중인데 문제 괜찮나요? 이감은...
-
방금 2방 맞았다
-
좀 마음을 가라앉히고 보는게 더 효율적인듯
-
빨리 수능보고싶다
-
사는 존재만이 알수있지 않을까
-
그렇게 어렵진 않습니다.
-
화작런 해서 2019 ~ 2024 3,4,6,7,9,10 다 풀음… 김승리 하프모고 풀까..
-
원래상태로 다시 되돌아갔네
-
영어가 너무 어렵네요 ㅠ 모고공부 팁좀
-
최저는 맞출 수 있음 수능 전 준비x 수시카드 한 장도 안 씀 보험용으로 써볼까요...
-
1인분도 못하고 어딘가에 기생해서 주변 사람 기운이나 빨아먹는 기생충같은데 앞으로도...
-
문열고 들어갈 것이다.
-
롤 서버 터졌나 16
롤체 해야 하는데 안들어가지네
-
생윤 커리 질문 4
경제 아닌거 같아서 런쳤고 지금 김종익 잘생긴 개념 60프로 들은 상태인데 이후...
질문 받나요??
남겨주시면 아는 선에서 답해드리겠습니다.
컴공에서 나이 많은 사람 몇살까지 보셨나요??
개인플레이가 지배적인 분위기라… 나이를 잘 모릅니다만 남자의 경우 26-28에 졸업하는 경우가 보편적이라고 생각은 합니다.