Q. N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.
어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.
각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.
입력.
첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다.
출력.
첫째 줄에 줄을 선 순서대로 키를 출력한다.
배열에 값이 있는지 체크하기 위해, 숫자가 저장되는 배열을 0으로 초기화시켜주고 시작한다.
이 문제는 두 개의 반복문을 사용하여 문제를 해결하였다.
1. 큰 수가 들어갈 수 있는 빈 공간을 남겨두는 것이 요점이므로, 빈 공간을 체크하는 반복문
2. 만약 조건을 만족한 자리에 다른 수가 있을 경우에 뒷 자리에 위치하게 하는 반복문
#include <stdio.h>
int main(void) {
int i, j, n, cnt;
int arr[10] = {0,};
scanf("%d", &n);
for (i = 0; i < n; i++) {
int tmp;
scanf("%d", &tmp);
j = 0; cnt = 0;
while(cnt != tmp)
if (arr[j++] == 0) cnt++;
while (arr[j] != 0)
j++;
arr[j] = i + 1;
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Q. 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
입력.
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력.
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
연속된 숫자들을 묶었을 때, 0의 묶음과 1의 묶음 중 작은 것을 출력하면 된다.
#include <stdio.h>
int main(void) {
int i, nOne, nZero;
char arr[1000001];
i = 0;
nOne = 0; nZero = 0;
while(1) {
scanf("%c", &arr[i]);
if (arr[i++] == '\n')
break;
}
i = 0;
while(1) {
if (arr[i] == '0') {
while (arr[i+1] == '0')
i++;
nZero += 1;
i++;
}
else {
while (arr[i+1] == '1')
i++;
nOne += 1;
i++;
}
if (arr[i] == '\n')
break;
}
if (nZero < nOne)
printf("%d\n", nZero);
else
printf("%d\n", nOne);
return 0;
}
Q. 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
입력.
첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력.
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
이 문제는 크게 k 개의 범위로 센서들을 모두 묶는 것과 같다고 할 수 있다. 즉, 아래와 같은 방법으로 문제를 해결했다.
" 센서 사이의 거리가 큰 순서로 k - 1개를 총 센서 사이의 거리에서 뺌. "
우선 고속도로 위의 센서들을 시각화하기 위해 입력받은 센서들의 위치를 정렬한다.
정렬을 한 후, 이웃한 센서 사이의 구하여 배열 ( arr_cmp )로 만들어 정렬한다. 마지막으로 이 배열의 인덱스 0 ~ k - 2를 갖는 요소를 총 센서 사이의 거리에서 빼준다.
#include <stdio.h>
#include <stdlib.h>
int int_cmp(const int *a, const int *b)
{
if (*a < *b)
return 1;
else if (*a > *b)
return -1;
else
return 0;
}
int main(void) {
int i, n, k, ans;
int *arr, *arr_cmp;
scanf("%d", &n); scanf("%d", &k);
arr = (int*)calloc(n, sizeof(int));
arr_cmp = (int*)calloc(n - 1, sizeof(int));
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
qsort(arr, n, sizeof(int), (int(*)(const void *, const void *))int_cmp);
for (i = 0; i < n - 1; i++) {
if (arr[i] != arr[i + 1])
arr_cmp[i] = (arr[i] - arr[i + 1]);
}
qsort(arr_cmp, n - 1, sizeof(int), (int(*)(const void *, const void *))int_cmp);;
ans = 0;
for (i = 0; i < k - 1; i++)
ans += arr_cmp[i];
if (n <= k)
printf("%d\n", 0);
else
printf("%d\n", (arr[0] - arr[n-1]) - ans);
free(arr); free(arr_cmp);
return 0;
}
Q. 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다.
토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽의 순서가 어긋나지 않도록 시합을 정한다. 물론 부전승을 임의로 만들 수 있지만, 토너먼트가 꼬여서는 안 된다. 또한, 각 시합에 임하는 두 선수의 랭킹의 차이의 합이 최소가 되도록 하려 한다.
예를 들어 추첨 결과가 차례로 랭킹 1, 6, 2, 5, 3, 4위의 선수들이었을 때의 토너먼트 세 개가 위에 있다. <A>의 경우는 각 시합이 (1 6), (2 5), (3 4), (1 2), (1 3)으로 랭킹 차이의 합이 5+3+1+1+2=12가 된다. 반면에 <B>는 11이, <C>는 10이 된다.
토너먼트 추첨 결과가 주어졌을 때, 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 프로그램을 작성하시오.
입력.
첫째 줄에 자연수 n(1≤n≤256)이 주어진다. 다음 줄에는 추첨 결과를 나타내는 n명의 선수들의 랭킹이 주어진다. 각 선수의 랭킹은 1부터 n까지의 자연수로 나타나며, 랭킹이 같은 경우는 없다고 가정하자.
출력.
첫째 줄에 답을 출력한다.
" 현재 배열에서 가장 큰 값 찾기 + 찾은 값의 왼, 오른 쪽에 있는 값 중 더 큰 값 찾기 "
두 선수의 랭킹 차이를 최소로 하기 위해서 두 랭킹값의 차이가 가장 작도록 해야하므로, 위와 같은 방식의 반복문을 사용하였다. 이 반복문을 한 번 돌 때마다 증가하는 변수 i 를 이용하여 배열의 인덱스 값을 조절하였다.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int i, j, n, ans = 0;
int *arr;
scanf("%d", &n);
arr = (int*)calloc(n, sizeof(int));
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int max, idx;
for (i = 0; i < n - 1; i++) {
int tmp = n - i;
max = 0;
for (j = 0; j < tmp; j++) {
if (max < arr[j]) {
max = arr[j];
idx = j;
}
}
int n_idx; // 배열의 최댓값 기준 양 옆에서 더 큰 수
if (0 < idx && idx < tmp - 1)
n_idx = (arr[idx + 1] >= arr[idx - 1]) ? arr[idx + 1] : arr[idx - 1];
else if (idx == 0)
n_idx = arr[idx + 1];
else
n_idx = arr[idx - 1];
ans += (max - n_idx);
for (int m_idx = idx + 1; m_idx < tmp; m_idx++)
arr[m_idx - 1] = arr[m_idx];
}
printf("%d", ans);
free(arr);
return 0;
}
Q. 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.
A의 앞에 아무 알파벳이나 추가한다.
A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.
입력.
첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.
출력.
A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.
이 문제는 아래와 같은 방법을 사용하여 해결할 수 있다.
" 문자열 b와 문자열 a의 차이가 가장 작을 때의 값을 찾는다. "
위와 같은 방법이 가능한 이유는 다음과 같다.
문제를 살펴보면, 문자열 a의 앞, 뒤에 새로운 문자를 추가할 수 있다고 한다. 즉 이것은 문자열 b와 동일한 문자를 추가할 수 있다는 뜻이므로, 기존의 문자열에서 차이의 최솟값을 구하라는 것을 의미한다고 볼 수 있다.
#include <stdio.h>
#include <string.h>
int main(void) {
int i, j;
char a[51], b[51];
scanf("%s %s", &a, &b);
int min = strlen(b);
for (i = 0; i <= strlen(b) - strlen(a); i++) {
int tmp = 0, cnt = 0;
for (j = i ; j < i + strlen(a); j++) {
if (a[cnt] != b[j])
tmp++;
cnt++;
}
if (min > tmp)
min = tmp;
}
printf("%d\n", min);
return 0;
}
Q. 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.
스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.
바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.
입력.
첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.
출력.
모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.
입력을 받는 과정에서 M < N 이라는 조건이 있으므로, do while 문을 이용하여 조건을 만족하도록 하였다.
이 문제는 아래를 큰 틀로 하였다.
" 바구니에 담을 수 있는 범위를 구하고, 그 안에 해당하는가 "
여기서 범위는 변수 l 과 r 을 이용하여 지정하였고, 한 번 반복문을 돌 때마다 pos 값을 변경시켜 그 값을 갱신하였다.
#include <stdio.h>
int main(void) {
int n, m, j;
do {
scanf("%d %d", &n, &m);
} while(m >= n);
scanf("%d", &j);
int pos = 1;
int ans = 0;
int l, r, tmp;
while(j--) {
l = pos; r = pos + m - 1;
scanf("%d", &tmp);
if (l > tmp) {
ans += l - tmp;
pos = tmp;
}
else if (r < tmp) {
ans += tmp - r;
pos = tmp - m + 1;
}
}
printf("%d\n", ans);
return 0;
}
