본문 바로가기

코딩테스트 연습/Baekjoon

 (78)
[Baekjoon] 9095번: 1, 2, 3 더하기 / dynamic https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net n:1 1 n:2 1+1 / 2 n:3 1+1+1 1+2 / 2+1 / 3 n:4 (1+1+1)+1 (1+2)+1 (2+1)+1 (3)+1 / (2)+2 (1+1)+2 / (1)+3 n일때, (n-1)의 모든 가지수에 1을 더한 횟수, (n-2)의 모든 가지수에 2를 더한 횟수, (n-3)의 모든 가지수에 3을 더한 횟수이므로 dp[i] = ( dp[i-1] + (dp[i-2] + dp[i-3]) 식으로 표현할 수 있다. 코드 //9095 #include #include using namespa..
[Baekjoon] 2225번: 합분해 / dynamic https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1 1 => 1, 2 1 => 1, 3 1 => 1, 4 1 => 1, 5 1 => 1, 6 1 => 1, 1 2 => 2, 2 2 => 3, 3 2 => 4, 4 2 => 5, 5 2 => 6, 6 2 => 7, 1 3 => 3, 2 3 => 6, 3 3=> 10, 4 3 => 15, 5 3 => 21, 6 3 => 28, 1 4 => 4, 2 4 => 14, 3 4 => 28, 4 4 => 35, 5 4 => 56, 6 4 => 84, ... 규칙을 보면 sum[n][k] = sum[n-1][k] + sun[n][k-1..
[Baekjoon] 2193번: 이친수 / dynamic https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 피보나치 배열이다. 1자리수일때 1개, 2자리수일때 1개, 3자리수 2개, 4자리수 3개... 부분문자열 11을 배제하면 끝자리가 1일때는 1개 추가, 끝자리가 0일때는 2개 추가 할 수 있으므로 피보나치로 배열이 만들어진다. int로는 자리수가 넘어가므로 long long배열에 저장했다. 코드 //2193 #include using namespace std; int main(int a..
[Baekjoon] 2156번: 포도주 시식 / dynamic https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net '연속으로 놓여 있는 3잔을 모두 마실 수는 없다' 라는 조건이 있으므로 예시 6, 10, 13, 9, 8, 1에서 최대 연속2개까지 고를 수 있다. i = 1일때 마실 수 있는 최대 포도주 양은 dp[1] = wine[1] 이므로 6이다. i = 2일때 dp[2] = wine[1]+wine[2] 이므로 16이다. i = 3일때 dp[3] = wine[1]+wine[2], wine[2]+wine[3..
[Baekjoon] 1932번: 정수 삼각형 / dynamic https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 조건 - 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 7 0층 3 8 1층 8 1 0 2층 2 7 4 4 3층 4 5 2 6 5 4층 예시의 삼각형을, 배열로 보면 triangle[0][0] = 7, triangle[1][0] = 3, triangle[1][1] = 8 ... 이다. dp배열에 현재 가질 수 있는 가장 큰 합을 저장한다. 0층에..
[Baekjoon] 1912번: 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net seq[i][0]에는 이전 인덱스 seq[i-1][0] 와 seq[i-1][1] 둘중 더 큰값을 저장한다. seq[i][1]에는 현재 들어오는 값 inp[i]와, seq[i-1][1] + inp[i] (누적 값) 을 비교하여 더 큰것을 저장한다. 마지막 배열 seq[n-1][0] 과 seq[n-1][1]를 비교하여 더 큰값이 최대 연속합이다. 코드 //1912 #include using namespace s..
[Baekjoon] 1699번: 제곱수의 합 / dynamic https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net i보다 작은 j의 제곱수를 찾으면, 제곱수는 항 최소개수가 1이므로 최솟값을 찾을 수 있다. i보다 작은 j의 제곱수를 찾고, square[i - (j*j)] + 1를 구하면 된다. n은 최대 100000까지 들어 올 수 있고, 2초 시간제한이 있으므로 j*j> n; for(int i=2;i
[Baekjoon] 16194번: 카드 구매하기 2 / dynamic https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 11052번과 거의 같은 문제다. 카드4개를 최솟값으로 뽑으려면 모든 카드팩을 뽑는 횟수를 생각해봐야 하므로 DP로 접근한다. dp[i-j]+p[j] 식을 이용하면, ( i개 카드를뽑은만큼 j카드 개수을 뺀 dp값 ) + ( j개 카드팩 ) 이므로 뽑는카드 개수보다(i) 카드팩의 개수(j)를 작게해서 모든 경우를 비교하여 작은 값을 dp[i]에 넣어준다. 그러면 dp[ 구매하려는 카드 개수 ] 에 최..

티스토리툴바