devlog

출처 : 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 방법 dp 문제로 dp의 인덱스로 몇 번째 집인지, 자신이 선택한 색의 인덱스를 저장해 준다 기저사례로는 index 가 N-1일 땐 전 집에서 선택한 색을 제외한 두 색중 작은 값을 return한다 기저사례가 아닐시 for 문을 돌며 금지된 색이 아닐때 재귀 호출로 다음 인덱스와 선택한 색을 호출하고 그중 작은 값과 자신이 선택한 비용을 return 하여 해결하였다. #inclu..

출처 : 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 ..

풀이 방법 dp 문제인데 문제를 부분 문제로 나누기 어려운 문제 였다. 처음에는 정사각형 하나를 두고 상하좌우로 사각형을 붙이는 형태로 부분 문제를 쪼개려고 생각 했지만 이러면 중복되는 부분을 다 제거 하기가 복잡해서 실패 했다. 정답은 층별로 부분 문제를 쪼개는 것이다 재귀 함수로 현재 남은 상자수와 각 재귀마다 첫 층에 쓸 상자수를 보내주고 함수 안에서 for 문을 돌며 2번째 층에는 몇개의 상자를 사용할지 선택후 함수 리턴값을 더하면 된다 여기서 리턴값에 first + second - 1를 곱해주어야 한다 1층과 2층을 한 칸씩 옆으로 이동시키면 다른 경우가 되기 때문이다. 시간 복잡도는 O(n^3)이다. #include #include #include #include const int MOD = ..

출처 : 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 방법 dp 문제이다 문제를 쪼개는 방법이 중요하다. 쪼갤 때 사각형의 가장 왼쪽 위 배열을 기준으로 그 정사각형의 한 변의 길이를 기록한다. 가장 큰 정사각형의 변의 길이를 제곱하여 넓이를 구한다. 0000 1111 1111 0000 예를 들어 위 경우에서 왼쪽 위 모서리의 배열에 길이를 저장이면 dp[1][0] = 2, dp[1][1] = 2.. 이렇게 되지만 dp[2][0] 은 1이 된다 변의 길이가 2인 정사각형에 포함은 되지만 그 정사각형에서 왼쪽 위의 점..

문제 고급 주택을 청소해주는 프리랜서가 있다. 최대한의 이익을 얻기 위해서 청소 스캐쥴을 짜야한다. 입력으로는 N이 주어지는데 N개의 청소할 수 있는 곳이 나온다 다음 N개의 줄에는 시작일, 마감일, 비용이 나오고 같은 비용일 때는 적은 일을 한 스캐줄이 선택 받는다. 주택을 옮기는데 비용이 들기 때문에 10만원이라는 지출이 발생한다. 일이 1일에서 3일까지 라면 3일 까지 일을 하는 것이기 때문에 3일에 일을 시작 할 순 없다. 해결 방법 dp 문제로 처음에는 일을 시작하는 날을 기준으로 cache의 인덱스를 정했지만 이러면 같은 날 시작하는 일이 2개 있을 경우 먼저 나온 일로 cache에 저장 되기 때문에 해결 할 수 없다. 그래서 일이 입력된 인덱스를 cache의 인덱스로 잡아 해결 하였다. 재귀..

문제 1부터 N까지 정수가 쓰인 N장의 카드 중 1~2장의 카드가 빠졌다 빠진 카드를 찾아라 (단 공간 복잡도는 O(1)의 공간 복잡도를 가져야 한다.) 빠지지 않은 카드의 번호는 무작위로 섞여 하나씩 제공된다. 풀이 방법 만약 카드가 1장 빠졌다면 1부터 N까지의 합(n*(n+1)/2) 에서 제공되는 카드수를 더 한 값을 빼면 빠진 카드의 수를 알 수 있다. 2장인 경우에는 식이 하나 더 필요하다 1부터 N까지의 제곱의 합이 필요하다 (n*(n+1)*(2n+1)/6) 에서 제공되는 카드의 수를 제곱한 것을 빼면 빠진 두 카드의 제곱의 합을 구 할수있다. 여기서 두 수를 더한 수의 제곱에서 두 카드의 제곱의 합을 빼면 수두의 2*곱한 값 을 알 수 있다. 두 수를 더한 값을 A 두수를 곱한 값을 B라고 ..

출처 : 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 방법 일을 할지 안 할지 선택하면 되는 dp 문제이다 문제의 입력을 받은데로 인덱스가 시작일 이므로 문제는 간단하다 다음 날 일을 시작하면 p[day]+Money(day + t[day]) 그냥 넘기려면 Money(day+1)을 해주어서 둘 중 max를 선택하면 된다. #include #include #include using namespace std; const int MAX = 15 + 1; const int INF = 987654321; int N; int cache[MAX]; int t[MAX]; int p[MAX]; int Money(..