devlog

출처 : 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 해결 방법 dp 문제로 n을 1, 2, 3을 빼서 재귀 호출을 반복적으로 하며, n이 0 이면 return 1을 n이 음수면 return 0을 해서 기저 조건을 만들어 주었다. dp table인덱스로는 숫자 n을 주었다. #include #include #include using namespace std; int dp[12]; int f(int n) { if (n == 0) return 1; if (n < 0) return 0; int& ret = dp[n]; if (ret != -1) ret..

출처 : 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해결 방법 dp문제 이다. top-down으로 해결 하였다. 3으로 나누어 지면 f(n/3)을 호출해서 저장하고 2로 나누어 지면 f(n/2)을 호출해서 저장하고 f(n-1)을 호출해서 저장해 가장 작은 값에다가 +1을 더해 주어서 리턴하였다. #include #include #include using namespace std; int dp[100001]; const int INF = 987654321; int f(int n) { if (n == 1) return 0; int& ret = dp[n]; int tree ..

출처 : algospot.com :: QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일 www.algospot.com 풀이 방법 정렬이 중요한 문제이다. 문제가 안 풀릴 시 정렬을 한번 생각해 보자 재귀 호출시 인자로 시작점과 남은 구간 자르기 횟수를 넘겨주면 된다 오차 제곱의 합을 구할 때 구간에서 평균값을 채택하면 구할 수 있다. 오차 제곱의 합의 값 계산은 구간 합 - 2 * 평균 * 구간 합 + 평균 * 평균 *(hi -lo +1)을 해주면 된다 여기서 hi 와 l..

출처 : 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 방법 dp 문제로 쉬운 문제였다. 재귀로 n을 입력받아 min(f(n-5), f(n-3)) + 1을 해주면 된다 기저 조건으론 n이 음수이면 INF(매우 큰 값)를 리턴해서 선택되지 못하게 n이 0이면 0을 리턴해서 끝났다는 것을 알려 주었다 마지막 출력부분에선 f(n)이 INF보다 크면 -1을 리턴 아니면 f(n)의 리턴 값을 리턴해 주면 된다 #include #include #include #include ..