무지개 달팽이

Q. 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.

상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.

이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.

바로 "45분 일찍 알람 설정하기"이다.

이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.

현재 상근이가 설정한 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 고쳐야 하는지 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 두 정수 H와 M이 주어진다. (0 ≤ H ≤ 23, 0 ≤ M ≤ 59) 그리고 이것은 현재 상근이가 설정한 놓은 알람 시간 H시 M분을 의미한다.

입력 시간은 24시간 표현을 사용한다. 24시간 표현에서 하루의 시작은 0:0(자정)이고, 끝은 23:59(다음날 자정 1분 전)이다. 시간을 나타낼 때, 불필요한 0은 사용하지 않는다.

출력.

첫째 줄에 상근이가 창영이의 방법을 사용할 때, 설정해야 하는 알람 시간을 출력한다. (입력과 같은 형태로 출력하면 된다.)

기본적으로 입력 받은 시간 중 변수 M에서 45를 뺀 결과를 구해야 한다.

여기서 주의해야 하는 곳은 (1-1) 변수 M의 값이 45 보다 작은 경우, (1-2)  변수 M에서 값을 빼기 위해, 변수 H의 값에서 1을 뺀 값이 0보다 작아지는 경우 이다.

위 두 경우를 조건문으로 한다.

#include <stdio.h>

int main(void) {
	int h, m;

	scanf("%d %d", &h, &m);

	if (m > 45)
		m -= 45;
	else {
		if (h == 0)
			h += 24;
		h--;
		m += 60;
		m -= 45;
	}

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

Q. 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력.

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

기본 베이스는 DFS 알고리즘을 이용했다.

우선 입력받은 컴퓨터의 번호 쌍을 바탕으로 인접 행렬을 구현한 뒤, 그리고 DFS 알고리즘에 적용하였다.

이 문제는 1번 컴퓨터로부터 웜 바이러스에 걸릴 수 있는 컴퓨터 수를 구하는 것이기 때문에, 

위 알고리즘에서 방문한 노드의 수 - 1 을 해주어야 한다.

#include <stdio.h>

#define SIZE 101

int visit[SIZE];
int a[SIZE][SIZE];

void dfs(int start, int n) {

    if (visit[start] == 1)
        return;
    
    visit[start] = 1;

    for (int i = 0; i <= n; i++) {
        if (a[start][i] == 1 && visit[i] != 1)
            dfs(i,n);
    }
}

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

    scanf("%d", &n);
    scanf("%d", &e);

    while(e--) {
        scanf("%d %d", &x, &y);

        a[x][y] = 1; a[y][x] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] != 1)
                    a[i][j] = 0;
            }
        }
    }
    
    dfs(1, n);

    ans = 0;

    for (int i = 2; i <= n; i++) {
        if (visit[i] == 1)
            ans++;
    }
    printf("%d", ans);
    
    return 0;
}

Q. 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력.

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력.

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

레벨이 올라갈수록 받을 수 있는 점수도 커지도록, 입력받은 수를 수정하는 문제이다.

즉, 중요한 것은 낮은 레벨의 점수가 높은 레벨의 점수보다 무조건 작아야 한다는 것이다.

문제에서 점수는 항상 양수이고, 항상 답이 존재한다고 하였으니까 arr[i] <= i + 1 인 경우는 없다.

그러므로 점수 배열 ( arr ) 에서 arr[i] > arr[i+1] 이 TRUE인 경우에만,

arr[i] 와 arr[i + 1] - 1의 차만큼 답에 더해주고, arr[i]의 값을 arr[i + 1] - 1으로 교체해주는 반복문을 만들어 준다.

#include <stdio.h>

int MAX(int a, int b)
{
    int max;

    if (a >= b)
        max = a;
    else
        max = b;
    
    return max;
}

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

    scanf("%d", &n);
    
    int arr[n];

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

    for (int i = n - 2; i > -1; i--)
    {   

        if (arr[i] >= arr[i+1]) {

            ans += arr[i] - (arr[i+1]-1);

            arr[i] = arr[i+1]-1;
        }

    }

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

    return 0;
}

Q. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력.

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력.

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

11053 번과 유사한 문제이다. 그래서 같은 코드를 제출하였더니, 시간 초과가 났다.

해결하기 위해 LIS 알고리즘에 대해 구글링해 본 결과, 수열의 크기가 전의 문제보다 더 크다는 점이 문제점이라는 것을 알아 냈다.

( ※ 참고 블로그 : https://jason9319.tistory.com/113 )

위 블로그를 통해 공부한 결과는 아래와 같다.

이 문제는 LIS 알고리즘을 이분 탐색의 방향으로 봐야 한다.

우선 특정 수열의 값을 정렬할 배열을 새로 하나를 만들어 주어야 한다.  위 블로그에서는 벡터를 이용하였는데, c언어를 사용하기 위해 stack 을 이용하였다.

이제 반복문을 사용하여, 수열의 값이 stack[top]의 값과 비교하는 과정을 거친다.

1. 수열의 값 < stack[top] 이면, 수열의 값보다 ① 크면서 ② 그 중에서 가장 작은 수와 자리를 교체해주는 lower_bound를 해준다.

2. 수열의 값 > stack[top] 이면, push 해준다.

3. 수열의 값 == stack[top] 이면, 이 과정을 뛰어 넘는다. ( = continue )

#include <stdio.h>

#define STACK_SIZE 1000000

int stack[STACK_SIZE];
int top = -1;

int isEmpty()
{
    if (top < 0)
        return 1;
    else
        return 0;
}

int isFull()
{
    if (top >= STACK_SIZE)
        return 1;
    else
        return 0;
}

void push(int x)
{
    if (isFull() == 0)
        stack[++top] = x;
}

int pop()
{
    if(isEmpty() == 0)
        return stack[top--];
}

int main(void)
{
    int n, tmp;

    scanf("%d", &n);

    int arr[n];

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

    push(arr[0]);

    for (int i = 1; i < n; i++)
    {
        if (stack[top] < arr[i]) 
            push(arr[i]);
        else if (stack[top] < arr[i])
            continue;
        else
        {   
            for (int j = top; j > -1; j--)
            {   
                if (arr[i] > stack[j])
                    break;

                tmp = j;
            }

            stack[tmp] = arr[i];
        }

    }
    
    printf("%d ", top + 1);
    
    return 0;    
}

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

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