Q. KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

 

입력.

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

 

출력.

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

 


 

최소 횟수로 아이들을 이동시켜서 번호 순서대로 줄을 세우는 문제이다.

 

번호 순서대로라고 하는 것은 오름차순으로 정렬하는 것과 같다. 이때, 유용하게 사용될 알고리즘이 있다.

바로 " 최장 증가수열 (= LIS 알고리즘) " 이다.

 

위 알고리즘은 한 수열에서 가장 긴 증가 수열의 길이를 구할 수 있다. 예를 들어, 10 50 30 40 이라는 수열이 있다고 하면, 가장 긴 증가 수열은 10 50 30 40 이다. 즉, LIS 값은 3이다.

 

이 문제에 적용해 본다면, 그 증가 수열에 해당하지 않는 나머지 수를 배열하면 되므로

 

 " N - LIS 알고리즘 결과 값 "

 

이 답이 되겠다.

 

※ LIS 알고리즘의 기본 예제가 되는 문제는 백준11053 번이다.

 

#include <stdio.h>

int main(void)
{
    int n, tmp = 0;

    scanf("%d", &n);

    int arr[n], dp[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for (int i = 0; i < n; i++)
    {   
        dp[i] = 1;

        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            
            	// 아래는 arr의 원소 값보다 작은 원소 값이 모두 count 되지 않도록 하는 조건문
                if (dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
        }

        if (tmp < dp[i])
            tmp = dp[i];
    }

    printf("%d", n - tmp);
    
    return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 2847번  (0) 2020.09.02
[C언어] 12015번  (0) 2020.08.30
[C언어] 1748번  (0) 2020.08.16
[C언어] 16194번  (0) 2020.07.15
[C언어] 9465번  (0) 2020.07.14

Q. 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

 

  • 설카드
  • 레드카드
  • 오렌지카드
  • 퍼플카드
  • 블루카드
  • 청록카드
  • 그린카드
  • 그레이카드

 

 

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

 

입력.

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

 

출력.

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.

 


 

※ 11052번과 쌍둥이 문제이다. 즉, ' [C언어] 11052번 ' 문제 풀이와 유사하다.

 

사야하는 카드팩에서 하나의 특정 카드팩을 샀을 때 남는 카드를 구매하는 방법을 배열 dp에 저장하는 방식으로 문제를 해결하였다.

 

#include <stdio.h>

int main(void) {
	int i, j, n;
	int min, tmp;
	int p[1001], dp[1001];

	scanf("%d", &n);

	for (i = 1; i <= n; i++)
		scanf("%d", &p[i]);

	dp[0] = 0;

	for (i = 1; i <= n; i++) {
		min = p[1] + dp[i-1];

		for (j = 2; j <= i; j++) {
			tmp = p[j] + dp[i - j];

			if (tmp < min)
				min = tmp;
		}

		dp[i] = min;
	}
	
	printf("%d", dp[n]);
	
	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 2631번  (0) 2020.08.17
[C언어] 1748번  (0) 2020.08.16
[C언어] 9465번  (0) 2020.07.14
[C언어] 2947번  (0) 2020.07.13
[C언어] 11052번  (0) 2020.07.12

Q. 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

 

입력.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

 

출력.

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

 


예제에 나온 스티커 점수를 표로 정리해보았다.

 

 

우선 인덱스가 작은 순서부터 스티커를 선택했을 때, 가질 수 있는 최댓값 ( 즉, 해당 스티커의 값 + 앞에서 최대 점수 값 ) 으로 값을 변경해준다. 그 결과는 아래의 표와 같이 나온다.

 

여기서 인덱스 0 ~ 1 까지는 직관적으로 구할 수 있는 부분이므로 배열 dp 에 값을 넣어준다.

 

그리고 인덱스 2 ~ ( n - 1 ) 까지는 다음과 같은 규칙으로 값을 변경시킨다.

 

행이 0 인 경우 : dp[1][i - 1] 와 dp[1][i - 2] 중 큰 수

행이 1 인 경우 : dp[0][i - 1] 와 dp[0][i - 2] 중 큰 수

 

위 규칙은 다음 표에 표시해두었다.

 

 

#include <stdio.h>

int main(void) {
	int i, j;
	int t, n;
	int dp[2][100000];

	scanf("%d", &t);

	while(t--) {
		scanf("%d", &n);

		for (i = 0; i < 2; i++)
			for (j = 0; j < n; j++)
				scanf("%d", &dp[i][j]);

		dp[0][1] += dp[1][0];
		dp[1][1] += dp[0][0];

		for (i = 2; i < n; i++) {
			dp[0][i] += (dp[1][i-1] > dp[1][i-2] ? dp[1][i-1] : dp[1][i-2]);

			dp[1][i] += (dp[0][i-2] > dp[0][i-1] ? dp[0][i-2] : dp[0][i-1]);
		}

		printf("%d\n", dp[0][n-1] > dp[1][n-1] ? dp[0][n-1] : dp[1][n-1]);
	}

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 1748번  (0) 2020.08.16
[C언어] 16194번  (0) 2020.07.15
[C언어] 2947번  (0) 2020.07.13
[C언어] 11052번  (0) 2020.07.12
[C언어] 1026번  (0) 2020.07.10

Q. 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

  • 설카드
  • 레드카드
  • 오렌지카드
  • 퍼플카드
  • 블루카드
  • 청록카드
  • 그린카드
  • 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

 

입력.

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

 

출력.

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

 


 

이 문제에서 중심이 되는 식은 다음과 같다.

 

" dp[ i ] = p[ j ] + dp[ i - j ] "

 

위 식은 " 총 사야하는 카드 수 = 구입한 카드팩 + 나머지 카드를 사는 방법 수 " 과 같다.

 

여기에 사야하는 카드는 변수 i,  구매할 카드팩은 변수 j로 이중 for문을 사용하였다.

 

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int i, j, n;
	int *dp, *p;
	
	scanf("%d", &n);

	dp = (int*)calloc(n+1, sizeof(int));
	p = (int*)calloc(n+1, sizeof(int));

	for (i = 1; i <= n; i++)
		scanf("%d", &p[i]);

	dp[0] = 0;

	for (i = 1; i <= n; i++) {

		int max = 0;

		for (j = 1; j <= i; j++) {
			if (max < p[j] + dp[i-j])
				max = p[j] + dp[i-j];
		}

		dp[i] = max;
	}

	printf("%d\n", dp[n]);

	free(dp);
	free(p);

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 9465번  (0) 2020.07.14
[C언어] 2947번  (0) 2020.07.13
[C언어] 1026번  (0) 2020.07.10
[C언어] 1316번  (0) 2020.07.09
[C언어] 1932번  (0) 2020.07.09

Q.

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력.

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

출력.

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 


 

이 문제는 아래와 같은 방식을 중심으로 배열을 재정리하였다.

 

" 삼각형 꼭대기의 값은 그대로 두고

아래로 내려오면서 대각선에 위치한 두 값 중 더 큰 것을 해당 값에 더한 결과로 변경 "

 

여기서 행에서 제일 앞과 뒤의 값은 따로 조건을 주어서 예외 상황을 해결하였다.

 

그리고 마지막 행일 경우에는 변수 ans를 이용하여 최댓값을 찾도록 하였다.

 

#include <stdio.h>

int main(void) {
	int i, j, n, ans;
	int dp[500][501] = {0,};

	scanf("%d", &n);

	for (i = 0; i < n; i++) 
		for (j = 0; j < i + 1; j++) 
			scanf("%d", &dp[i][j]);

	ans = 0;
	for (i = 1; i < n; i++) {
		for (j = 0; j <= i; j++) {
			if (j == 0)
				dp[i][j] += dp[i-1][j];
			else if (j == i)
				dp[i][j] += dp[i-1][j-1];
			else 
				dp[i][j] += (dp[i-1][j-1] >= dp[i-1][j] ? dp[i-1][j-1] : dp[i-1][j]);
	
			if (i == n - 1)
				if (ans < dp[i][j])
					ans = dp[i][j];
		}
	}
	
	printf("%d\n", ans);

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 1026번  (0) 2020.07.10
[C언어] 1316번  (0) 2020.07.09
[C언어] 11727번  (0) 2020.07.07
[C언어] 1138번  (0) 2020.07.07
[C언어] 9095번  (0) 2020.06.24

Q. 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력.

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력.

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 


 

n 값 별로 그림을 그려보았을 때, 블록의 마지막은 길이가 1이 남거나 2가 남는다는 것을 알 수 있다.

 

그리고 길이 2의 경우에는 2 X 1 블록과, 2 X 2 블록이 올 수 있으므로 다음과 같은 식을 구할 수 있다.

 

dp[n] = dp[n - 1] + dp[n - 2] * 2

 

여기서 n의 값이 커질 수록 배열에 들어가는 값도 상당히 증가할 수 있으니,

int형 범위를 넘지 않도록 배열에 값을 넣어줄 때 10,007로 나눈 나머지를 그 값으로 해주었다.

 

#include <stdio.h>

int main(void) {
	int i, n, dp[1001];

	scanf("%d", &n);

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 3;

	for (i = 3; i <= n; i++)
		dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;

	printf("%d\n", dp[n]);

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 1316번  (0) 2020.07.09
[C언어] 1932번  (0) 2020.07.09
[C언어] 1138번  (0) 2020.07.07
[C언어] 9095번  (0) 2020.06.24
[C언어] 1439번  (0) 2020.06.10

Q. 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력.

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 


 

 

규칙에 맞춰서 생각을 해보면 dp[n] = dp[i-1] + dp[i-2] + dp[i-3] 이라는 식을 유추해낼 수 있다.

 

dp 배열에 0, 1, 2의 값을 부여하지 않는 코드를 짤 때는 n이 음수로 될 경우에 값이 0이 되도록 해야할 것이다.

 

#include <stdio.h>

int main(void) {
	int i, n, tmp, dp[11];

	scanf("%d", &n);

	while (n--) {
		scanf("%d", &tmp);

		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;

		for (i = 3; i <= tmp; i++)
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

		printf("%d\n", dp[tmp]);
	}

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 11727번  (0) 2020.07.07
[C언어] 1138번  (0) 2020.07.07
[C언어] 1439번  (0) 2020.06.10
[C언어] 2212번  (0) 2020.06.05
[C언어] 2262번  (0) 2020.06.03

+ Recent posts