무지개 달팽이

Q. 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력.

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

출력.

첫째 줄에 새로운 수의 자릿수를 출력한다.

1부터 입력받은 n 까지 나열한 수를 하나의 수로 볼 때, 그 수의 자리수를 구하는 문제이다.

즉, 1을 n 까지 증가시키면서 자리수를 카운트해주면 된다.

자리수는 10, 100, ~ 100,000,000 일 때 변경되므로 이 규칙을 조건문으로 구현하였다.

#include <stdio.h>

int main(void)
{
    int n, x, ans;

    scanf("%d", &n);

    x = 1, ans = 0;

    while(x <= n)
    {
        if (x < 10) ans += 1;
        else if (x < 100) ans += 2;
        else if (x < 1000) ans += 3;
        else if (x < 10000) ans += 4;
        else if (x < 100000) ans += 5;
        else if (x < 1000000) ans += 6;
        else if (x < 10000000) ans += 7;
        else if (x < 100000000) ans += 8;
        else ans += 9;

        x++;
    }

    printf("%d\n", ans);
    
    return 0;
}

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;
}

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;
}

Q. 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력.

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

버블 정렬 알고리즘을 구현하는 문제이다. 

단, 문제가 요구하는 것은 인덱스가 작은 순으로 정렬하는 것이기 때문에 이것을 주의해야 한다.

#include <stdio.h>
#define swap(type, x, y) do {type t = x; x = y; y = t;} while(0)

void bubble(int a[], int n) {
	int i, j, tmp;
	
	for (i = n - 1; i > 0; i--) {

		for (j = 0; j < i; j++)
			if (a[j] > a[j+1]) {
				swap(int, a[j], a[j+1]);

				for (tmp = 0; tmp < 5; tmp++)
					printf("%d ", a[tmp]);

				putchar('\n');
			}
	}
}

int main(void) {
	int i;
	int n[5];

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

	return 0;
}

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;
}

Q. 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력.

첫째 줄에 S의 최솟값을 출력한다.

( 배열 A의 요소 ) X ( 배열 B의 요소 ) 의 형태로 만들어 그 합의 최솟값을 구하는 문제이다. 

이 문제는 아래와 같은 두 가지 방식으로 접근했다.

※ 정렬은 버블정렬을 이용하였다.

①

문제에는 배열 B는 재배열 하지 않는다는 조건이 있지만, 단순히 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있다.

배열 B의 요소값은 큰 순서대로 배열 A의 요소값이 작은 순서대로 정렬

+

후에 곱하여 모두 더함

즉, 정렬 알고리즘만을 이용하여 해결한 경우이다.

#include <stdio.h>

#define swap(type, x, y) do{type t = x; x = y; y = t;} while(0)

void a_bubble (int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] > a[j])
				swap(int, a[j - 1], a[j]);
}

void b_bubble(int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] < a[j])
				swap(int, a[j - 1], a[j]);
}

int main(void) {
	int i, n, ans = 0;
	int a[50], b[50];

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

	a_bubble(a, n);
	b_bubble(b, n);
	
	while (n--) 
		ans += (a[n]*b[n]);

	printf("%d\n", ans);
	
	return 0;
}

Q. 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력.

첫째 줄에 그룹 단어의 개수를 출력한다.

순서대로 사용한 알파벳에는 방문 체크를 해두었다가, 다음 방문 시 체크 여부를 확인하여

방문 한 경우 변수 N 값을 감소하면서 총 그룹 단어 개수를 구하였다.

방문 여부는 배열 alpha를 이용하였다.

#include <stdio.h>
#include <string.h>

int main(void) {
	int i, n, ans, tmp;
	char word[101];
	
	scanf("%d", &n);

	ans = 0;
	
	int cnt = n;

	while(cnt--) {
		scanf("%s", word);

		tmp = word[0] % 97;

		int alpha[26] = {0,};

		for (i = 1; i < strlen(word); i++) {
			if (tmp != word[i] % 97) {
				if (alpha[word[i] % 97] != 0) {
					n--;
					break;
				}
				else {
					alpha[tmp] = 1;
					tmp = word[i] % 97;
				}
			}
		}
	}

	printf("%d\n", n);

	return 0;
}

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;
}