동동매니저의 생활

★ solved.ac 난이도 : S1 (작성 시점 기준) [문제 본문 링크] 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 일반적인 동적 계획법(DP) 문제이며, BOJ #1463 (1로 만들기) 문제에서 역추적을 추가한 문제입니다. 먼저 크기가 100만 이상인 충분한 정수 배열 2개를 만듭니다. (배열의 이름은 dp로 설정하며, 정답 계산용[0]과 역추적용[1]으로 구분합니다.) 입력이 1이면 연산이 필요하지 않으므로 정답은 0입니다. (dp[1][0] = dp[1][1] = 0) 2 이상의 입력에 대해서는 문제의 조건에 따라 3가지로 생각할 수 있습니다. 경우 1. x가 3으로 나누어 떨어지면서 dp..

★ solved.ac 난이도 : S3 (작성 시점 기준) [문제 본문 링크] 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 일반적인 동적 계획법(DP) 문제입니다. 먼저 크기가 100만 이상인 충분한 정수 배열을 만듭니다. (배열의 이름은 dp로 설정하며, 이 배열에 정답을 계산해 저장합니다.) 입력이 1이면 연산이 필요하지 않으므로 정답은 0입니다. (dp[1] = 0) 2 이상의 입력에 대해서는 문제의 조건에 따라 3가지로 생각할 수 있습니다. 경우 1. x가 3으로 나누어 떨어지는 경우 3으로 나누기 : min(dp[x], dp[x/3]+1)을 계산합니다. (여기에서 +1은 1번의 추가 연산을 의미합니다...

★ solved.ac 난이도 : S3 (2021년 12월 29일 기준) [문제 링크] 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [문제 분석] 피보나치 수를 찾는 또 다른 방법을 생각해보는 문제 [풀이] 이 문제의 함정은, 본문에 나와있는 그대로 하면 되겠지... 라고 생각하신다면 큰 코 다칩니다. 시간 초과가 뜨기 때문이죠... 여기에서는, 반복문을 통해서 풀어보려고 합니다. n번째 피보나치 수를 fib(n)이라고 하면, fib(0) = 0 fib(1) = 1 fib(n) = fib(n-2)+fib(n-1) (단, n>1) 이 성립합니다. 여기에서는, (n-1)번째 수와 n번째 수를 출력하시면 됩니..