이번에는 난이도를 한 단계 낮추어 참여하였다.
목표는 전의 contest에서 나의 부족함이 무엇이었는지 찾아내려고 했다.
A. Candies
풀이 보기
풀이
간단한 수학 문제이다. 주어진 식에서 $x+2x+4x+…+2^{k-1}x=(2^k-1)x$이므로, 숫자를 2배씩 늘려가면서 나누어 떨어지는 수가 있는지만 검사하면 된다.
답이 있다고 보장되었으므로, 무한 반복문을 통하여 답을 도출하는 가정도 가능하다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main(t)
{
for (scanf("%d", &t); t; t--)
{
long long n;
scanf("%lld", &n);
long long x = 4;
while (1)
{
if (!(n % (x - 1)))
{
printf("%lld\n", n / (x - 1));
break;
}
x *= 2;
}
}
return 0;
}
B. Balanced Array
풀이 보기
풀이
배열 $a$의 앞부분 $n/2$개의 원소는 짝수, 뒷부분 $n/2$개의 원소는 홀수이다.
모든 원소가 달라야한다는 조건이 있지만, 이 부분은 임의적으로 맞춰넣을 수 있으므로, 풀이에는 배제하여도 상관 없다.
배열의 앞부분과 뒷부분의 각 합이 같아야한다는 조건을 유심히 보아야 한다. 만약 $n/2$이 홀수라면 배열의 앞부분은 짝수, 뒷부분은 홀수가 나올 것이므로, 서로 다른 값을 나타낼 것이다. 이 조건을 만족하기 위해서는 $n/2$가 짝수여야한다. 다른 말로 하면 $n$은 4로 나누어 떨어져야한다.
만약 답이 YES라면 그 배열의 값도 출력하여야 한다. 이 부분은 임의로 넣어도 상관 없는데, 나의 경우는 아래와 같이 풀이하였다.
- 짝수 부분의 경우는 $2,4,6,8,…$으로 순서대로 작성하였다.
- 홀수 부분의 경우는 앞에는 $1,3,5,7,…$으로 순서대로 작성하고, 가장 마지막 수는 짝수 부분과의 합을 같게 만들기 위해 $n/2$를 더해주었다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
int main(t)
{
for (scanf("%d", &t); t; t--)
{
int n;
scanf("%d", &n);
if (n % 4)
printf("NO\n");
else
{
printf("YES\n");
int i;
for (i = 1; i <= n / 2; i++)
printf("%d ", i * 2);
for (i = 1; i < n - 2; i += 2)
printf("%d ", i);
printf("%d\n", i + (n / 2));
}
}
return 0;
}
C. Alternating Subsequence
풀이 보기
풀이
주어진 배열 $a$에서 순서를 바꾸지 않고 여러 원소를 제거한 배열 $b$를 만들어야한다.
$b$의 조건은 아래와 같다.
- $b$의 원소는 앞뒤가 다른 부호여야 한다. (양-음-양, 음-양-음)
- $b$의 길이는 가능한 subsequence중 가장 길다.
2번 조건을 만족하기 위해서는 순차로 탐색하다 부호가 변하는 시점에서는 무조건 값을 배열에 넣어야 한다. 1번 조건을 만족하기 위해, 부호가 변하기 전까지의 숫자들 중 가장 큰 값을 선정하여 그 값만을 $sum$으로 취한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
int main(t)
{
for (scanf("%d", &t); t; t--)
{
int n;
scanf("%d", &n);
long long input;
scanf("%lld", &input);
long long sum = 0;
long long temp = input;
int isPlus = (input > 0);
for (int i = 1; i < n; i++)
{
scanf("%lld", &input);
if (isPlus == (input > 0))
{
if (temp < input)
temp = input;
}
else
sum += temp, temp = input, isPlus = 1 - isPlus;
}
sum += temp;
printf("%lld\n", sum);
}
return 0;
}
결과
| Contest | Start time | Rank | Solved | Rating change | New rating |
|---|---|---|---|---|---|
| #636 (Div.3) | 2020/4/21 23:35 | 2052 | 3 | +83 | 1407 |
이번에 Specialist 단계로 진입하였다. 확실히 Div.2 때보다는 더 많은 문제를 풀어낼 수 있었고, 문제 이해도 능숙하지는 않지만 원하는 바를 알아내는데 오래 걸리지 않았던 것 같다.
나의 실력이 아직 Div.2를 능숙하게 다룰 정도로 좋지는 않다는 것을 깨달았다. contest에 열중하는 것도 좋지만 나의 기본기를 더 기르고 참여하는 것이 좋을 것 같다고 생각한다.
백준 사이트에서 실력을 더 기르고 contest에 임해야겠다.