https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 1차원 DP 문제였다. 피보나치 함수(이하 fibo) 의 호출횟수를 수동으로 살펴보도록 하겠다. fibo[0] = 1 fibo[1] = 1 fibo[2] = 3 fibo[3] = 5 fibo[4] = 9 .... 규칙을 파악할 수 있는가? fibo[k] = (1+fibo[k-1]+fibo[k-2]) 이다. 1은 자기자신 역시 호출되었기에 더해줘야 하는 수고 fibo[k-1]과 fibo[k-2] 는..
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 고민을 오래 해봐야 하는 문제 수의 범위가 크다. 일단 수의 범위가 매우 큰 편이라서, 전처리를 통해서 시간을 아낄 생각을 해봐야 한다. 대부분의 변수에서 long long 형이 필요하니까, 그냥 모든 변수 자료형을 ll으로 통일하면 깔끔해진다. cnt[k] 를 비트 k개 범위(0~2^k-1) 의 수들에서 등장하는 2진수 1의 개수의 합 으로 정의한다. 숫자 K가 i개의 ..
https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 www.acmicpc.net DP 사용해서 해결한 문제. dp[k] : k명까지 조를 짰을때 잘 짜여진 정도의 최댓값 으로 정의한다. 또한, 인덱스 s부터 e까지의 사람들로 조를 편성했을때 조가 잘 짜여진 정도를 O(N) 에 구해내는 함수를 하나 작성하고, (for문을 통해 만들면 된다) 이를 cal(s,e)라고 정의한다. dp[1]은 당연히 0이 될 것이고, $k$보다 작거나 같은 수 $a$에 대해서 dp[a-1] +..
https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net DP로 해결했던 문제 DP[i][j] 를 $(i,j)$ 까지 이동해서 채취할 수 있는 최대 자원 으로 정의한다. $(i,j)$ 로 이동하는 경우는 $(i-1,j)$ 에서 이동한 경우 $(i,j-1)$ 에서 이동한 경우 두가지 경우가 있으므로, DP[i][j] = MAX( DP[i-1][j], DP[i][j-1] ) + arr[i][j] 로 계산해주면 정답을 얻을 수 있다. D..
https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 깔끔하게 풀어서 맘에드는문제 그래프 or 다익스트라로 푼 사람들이 몇몇 보이던데, 개인적으로는 DP로 푸는게 더 깔끔하지 않나 싶다. $dp_i$ - 현재 위치가 i 일때 운전한 거리의 최솟값 다음 dp테이블의 정의에 따라 정답은 $dp_D$ 가 된다. $dp_k$ 는 처음에 임의의 MAX값( 난 998244353으로 정했다 ) 로 초기화해놓은 뒤, 두가지 경우 지름길이 없는 경우 $d..
DP + BFS 문제. https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net dp[k] 를 숫자 $K$를 만드는데 필요한 최소한의 버튼 누름 횟수 라고 하고, 숫자 $K$인 상태에서 두 버튼을 눌렀을때 변화하는 수를 각각 $A(K)$, $B(K)$ 이라고 하면 dp[A(K)] = dp[k] + 1 dp[B(K)] = dp[k] + 1 이 된다. 버튼 A, B를 누를 때 각각 숫자가 99,999..