dynamic
-
[BOJ] 2342 Dance Dance RevolutionPS/BOJ 2020. 7. 20. 00:28
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마�� www.acmicpc.net 알고리즘: DP 시간복잡도: $O(N)$ 접근: 1. 사용되는 최소의 힘을 구하라 -> 이 문제를 읽어보면 brute-force를 사용하는 naive한 풀이를 떠올릴 수 있다. (어떠한 상태를 갱신해 내가면서 최선의 답 찾기) 허나 N 제한이 10^5이기 때문에 무조건 TLE가 발생하게 된다. 따라서, 1번 조건을 주목해 보았다. 최소의 힘을 구하라고 하는걸 ..
-
[BOJ] 1932 정수 삼각형PS/BOJ 2020. 7. 16. 20:14
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2) 접근: 1. 이전 값들을 참고하면서 갱신하는 것이므로 Dynamic 문제 $$D[k]=MAX(D[k-i-1],\ D[k-i])+a_k$$ 주의) 각 층의 양 끝점은 한 쪽 대각선이 없으므로 이를 예외 처리해줘야 함. 더보기 #include int main() { int N, a, i, j, k, D[500*500], max..
-
[BOJ] 1912 연속합PS/BOJ 2020. 7. 16. 19:48
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N) 접근: 1. 연속합의 최댓값 구하기 수열의 특정 부분을 봤을 때, 이 수가 최대 연속합의 일부가 될 가능성이 있다는 것을 알 수 있을까? 일단 수열의 수들을 계속 더해나가자... 만약에 수가 양수일 시, 이들을 계속 더하다보면 최댓값에 도달할 것이다. 하지만, 이 문제는 중간 중간에 음수들이 섞여있다. 따라서 계속 더해 나가다가 부분합이 0보다 작아지게 되면, 차라리 다..
-
[BOJ] 1904 01타일PS/BOJ 2020. 7. 16. 19:37
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 알고리즘: DP, Math (Fibonacci number) 시간복잡도: 1. O(N) 2. O(p) (p = 47244, Pisano Period) 접근: 1. 1, 00 타일로 만들 수 있는 길이가 N인 수열의 모든 가짓수 2. 타일을 붙여서 점점 길이를 확장 (부분문제) -> 1, 2번 조건을 통해 Dynamic으로 접근할 수 있음을 알 수 있다. D[N]: 길이가 N인 수열을 만들 수 있는 ..
-
[BOJ] 12851 숨바꼭질 2PS/BOJ 2020. 7. 16. 18:15
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(V+E) BOJ 1697 숨바꼭질의 업그레이드 버전이다. https://moon323.tistory.com/16 N에서 K까지 이동하는데 걸리는 최단 시간뿐만 아니라 그 방법의 가짓수도 구해야한다. 접근: 1. 가짓수 구하기 -> 가짓수 구하는 문제이므로 Dynamic을 이용하면 된다. D[i]: i 좌표까지 가는 ..
-
[BOJ] 1562 계단 수PS/BOJ 2020. 7. 16. 15:53
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2 * 2^10) https://moon323.tistory.com/12 쉬운 계단 수의 심화문제이다. 0~9까지 모든 수가 자리수에 등장 이라는 조건만 추가되었다. 조합을 묻는 문제에서 on / off (등장, 비등장)을 묻는 문제는 비트연산을 이용해주면 빠르고 깔끔하게 해결 가능하다. 예를 들어, 이 문제 같은 경우 10bit를 만들어서 등장하는 수가 있으면 해당 bit를 1로 켜주면 된다. (or 연산) ex) b = 0000000000 1) 1 등장: b | (1
-
[BOJ] 10844 쉬운 계단 수PS/BOJ 2020. 7. 16. 12:21
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N) 접근: 1. 계단 수가 총 몇 개 인지 구하기 (가짓수) 2. 계단 수 조건: 인접한 자리 수의 차이가 1 -> 1,2 번 조건 모두 Dynamic을 이용하기 좋은 조건들이다. 1번은 보통 DP 문제들의 패턴이고 2번도 부분문제로 접근할 수 있기 때문이다. 2번 조건을 DP로 접근해보면, N+1 자리수의 계단 수는 마지막 자리를 제외한 나머지 N 자리수도 계단 수를 만족해야한다. 따라서, N+1 자리수의 계단 수를 계산하려면 N 자리수 계단수부터 계산해야 하고 결국 bott..
-
[BOJ] 1520 내리막 길PS/BOJ 2020. 7. 16. 11:59
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(NM) 접근: 1. 지도가 주어지고 경로 탐색 2. 가능한(내리막길) 경로의 개수 구하기 -> 경로탐색은 보통 BFS로 접근하고, 가능한 가짓수를 구하는 문제는 보통 Dynamic으로 접근한다. D[i][j]: (i, j) 까지 가능한 경로의 가짓수 라고 하면, $$D[i][j] = \sum_{k=0}^N D[y_k][x_k]$$ $$(y_k,x_k):\..