[백준 1520] 내리막 길

[ 백준 1520 : 내리막 길 ]

왼쪽 제일 위에서 오른쪽 제일 아래까지 이동할 수 있는 경로의 경우의 수를 찾는 문제이다.
만약 그냥 가는 것이라면 다이나믹 프로그래밍으로 처음 좌표의 값은 0 일 것이고 붙어있는 두 개의 좌표에는 1
그다음 붙어있는 좌표는 1 또는 2 이런식으로 값을 집어넣어서 마지막 (n-1,m-1)좌표에 있는 값만 구하면된다.

그런데 문제에서 요구하는 것은 현재의 좌표보다 다음 좌표에 있는 숫자가 무조건 작아야한다. 이렇게 나오면 뭐 평소에 BFS나 DFS 풀 때 VISIT변수를 둬 방문했는지 안했는지를 체크할 필요가 없다.

왜냐하면 다음 좌표로 가는 조건을 현재 좌표의 수>다음 좌표의 수 이기때문에 절대로 다음 좌표에서는 현재좌표로 올 수 없기때문이다.
그럼 이제 어떻게 풀 것인지 알아보면 물론 다이나믹 프로그래밍이다.

한 좌표마다 (N-1 , M-1)로 가는 경우의 수를 넣으면 된다.
평소 DP를 푸는 방식으로 재귀적으로 DP를 구현했다.

[백준 2629] 양팔저울

[ 백준 2629 : 양팔저울 ]

처음에 문제를 보고 단순히 전체 계산하면 된다고 생각했다.
어짜피 나올 수 있는 수는 0부터 15000 사이였고 이 나올 수 있는 무게 중 구슬 무게가 있으면 Y 없으면 N 을 출력하도록했다.

나는 이런 메모이제이션 문제를 풀 때 항상 푸는 틀? 같은게 있는데 이번엔 그렇게 풀지 않고 FOR문으로 돌면서 풀려고 시도했다.
근데 계속 틀려서 그냥 풀던 방식 재귀로 푸니까 풀렸다.....뭘 잘못했나보다..

로직은
SUM이라는 이차원 배열을 놓고 추를 0개 올렸을때 + 1개 올렸을 때 ... + 다 올렸을때의 모든 체크가 마지막 배열에 담겨있다.

PRESUM이라는 함수는
(다음 추 , 현재추 + 현재까지의 무게 )
(다음 추 , 현재까지의 무게)
(다음 추 , 현재 무게에서 현재 추를 왼쪽으로 옮겼을때)
이렇게 재귀적으로 돌며 모든 가능한 수를 체크한다.

한번 체크했던 무게라면 바로 반환을 하며 함수를 끝내준다. 시간을 절약한다.

[백준 1756] 피자 굽기

[ 백준 1756 : 피자 굽기 ]

오븐의 깊이 = 30만 피자 갯수 = 30만
딱 봐도 일반적인 탐색으로는 시간초과가 나올것 같다.
피자 입력이 한 개가 들어올때 오븐 처음 인덱스부터 마지막인덱스까지 입력보다 작은 값을 가진곳에서 break; 하는 탐색은 최악에 30만 * 30만...

그럼 어떻게 할까? 일단 이진탐색으로는 안될 것같다. 오븐배열을 정렬해버리면 안되니까.. 더 효과적인방법??
DP를 이용한다.
오븐 한 인덱스마다 지금까지 나온 최솟값을 집어넣는다.
테스트케이스인 5 6 4 3 6 2 3를 보면
5
5 5
5 5 4
5 5 4 3
5 5 4 3 3
5 5 4 3 3 2
OVEN = {5 5 4 3 3 2 2}
ㅇㅣ렇게 오븐배열에 저장한 뒤 이진탐색으로 찾는다.
만약 못찾을때 바로 0을 출력하고 프로그램을 종료시키면된다.

[백준 5549] 행성 탐사

[ 백준 5549 : 행성 탐사 ]


백준에 기본 DP문제 중
[백준 11660 : 구간 합 구하기 5 ] 이 문제와 똑같은문제입니다.

(A,B)~(C,D)의 직사각형안에 있는 J와 O와 I의 갯수를 뽑아야합니다.
한 좌표마다 그 전 까지의 상태를 저장해놓고 출력하는 문제인데
이번 문제는 한 좌표마다 3개의 상태를 저장해야하니까 SUM[X][Y][3]이런식으로 저장하면됩니당

그럼 상태는 어떻게 정의될까 한번 식으로 봐보면

SUM[X][Y] = 현재좌표 + SUM[X-1][Y] + SUM[X][Y-1] - SUM[X-1][Y-1]

사각형이 (0,0)~(X,Y)라고 했을때
현재좌표 + (X-1,Y)까지의 상태 + (X,Y-1)까지의 상태 - 겹치는부분(X-1,Y-1) 이렇게하면
현재좌표마다의 총 합이 구해집니다.

그럼 (A,B)~(C,D)의 합은????
현재 좌표마다 (0,0)~(C,D)까지의 합들이 구해져있으니까 (0,0)~(C,D)-(0,0)~(A,B)를 해주면됩니다.
식으로 표현하면

=>SUM[C][D] - SUM[A-1][D] - SUM[C][B-1] + SUM[A-1][B-1]

(C,D)까지의 합에서 0부터 A행위까지의 합을 빼고 0부터 B열왼쪽까지의 합을 빼고 겹치는 부분을 빼줬으니 다시 더해줍니다.(A-1,B-1)

이런식으로 풀면 답이 뽜봣!

[백준 10265] MT

[백준 10265 : MT ]

꼭 이런친구들 있다...

사람 수 N과 버스에 태울 수 있는 사람 수 K가 주어지고 (1<=K<=N<=1000) 각 사람(Xi[n])들의 연관성이 주어진다.
의견을 해치치않고 최대한 태울 수 있는 인원 수를 출력하는 문제인데 
나는 dp+dfs방식으로 풀었다.

개인과 연관된 사람들의 묶음이 필요하다고 느껴 dfs를 썼고
0번 사람을 태웠을때 누가 더 탈 수 있는지 1번 사람을 태웠을 때 누가 더 탈 수 있는지 모든 정보가 필요해서 메모리제이션을 이용해 최대 태울 수 있는 인원 수를 구했다.

학생들은 서로 방향성을 가진 그래프로 표현이된다.
그러므로 벡터에 넣어줄때 일방향으로만 넣어주면된다.

DP로 풀 것이므로 메모이제이션할 배열의 크기 설정을 해준다.
한 학생의 묶음은 1000명까지 가능하다.
학생은 총 1000명까지 된다. 그러므로 1000x1000으로 잡아준다.

그리고 이제 1번 학생부터 본다. 1번 학생과 같이 타야하는 학생들을 구해준다.
만약 k보다 작거나 같다면? 다음 인덱스로 갈 수 있다.
이때 태웠을때와 안태웠을때로 갈라지면서 재귀를 들어간다.
그럼
재귀(다음 인덱스, 현재까지 태운 학생) 와
재귀(다음 인덱스, 현재까지 태운학생+방금 계산한 묶음)
이렇게 들어갈 수 있다.
재귀의 종료시점은 인덱스가 N에 도달했을때 이다.

이런식으로 풀어줬는데 한번 DP의 깊이에 들어갈때마다 태울지 말지를 결정하는 부분이
처음에 헷갈려서 초반에 난감했던 문제였다.

냅쌕알고리즘을 공부하고 왔더니 다시 봤던 문제인데
먼저 냅쌕을 풀고 온다면 쉽게 풀 수 있는 문제다.