Karatus::[19.06.26] Codeforces Round #570 (Div. 3) 참가 후기

Codeforces Div.3을 우리나라 시간으로 오후 11:35에 시작해서 2시간 동안 진행했습니다.

이번에 처음 참가하는 Contest여서 엄청 긴장했었습니다.

그리고 오후 늦게 진행되다 보니 졸리지 않도록 유지하는 것도 하나의 일이었습니다.

처음으로 참가하는 사람을 위한 Div. 3 부문이어서 이전 문제들을 조금 살펴봤습니다만,

생각보다 조금 어려웠던 난이도에 뒷부분은 Div. 2 가기 직전인 사람들을 위한 변별력 문제를 많이 내는 느낌이었습니다.

그래도 평소 백준에서 풀던 실력을 믿고(?) 도전하기로 마음을 먹고 드디어 Contest가 막을 열었습니다.

( ※ 스포가 싫으신 분들은 뒤로 가기 살짝... )

A. Nearest Interesting Number

간단히 말해서 '어떤 정수의 각 자리수를 더한 값이 N으로 나누어진다면, 원래 정수도 N으로 나눠지는 흥미로운 수가 있다'라는 것입니다.

그래서 3으로 나눠지는 흥미로운 수가 있다는 걸 아는데, 이번에는 4라는 숫자로 만족되는 흥미로운 숫자를 찾고 싶다는 것입니다.

Input으로 주어진 수가 흥미로운 수인지를 밝히고, 그렇지 않다면 주어진 값과 가장 가까운 크거나 같은 수를 찾아 그 수를 출력하라는 뜻입니다.

저는 이 문제를 다 읽고 Input 값의 범위도 1 ~ 1,000으로 작겠다 싶어서 딱히 다른 수학적 수식은 생각지 않고 바로 코드를 구현했습니다.

#include <cstdio>

int sumOfNum(int n) {
    int sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int n;
    scanf("%d", &n);
    
    while(true) {
        if(sumOfNum(n) % 4 == 0) {
            printf("%d", n); break;
        }
        else sumOfNum(++n);
    }
}

다음에는 이런 간단한 문제에서 시간을 좀 더 줄여야겠더군요. 7분이나 걸렸습니다 ㅜㅠ

B. Equalize Prices

사실 풀고 나면 A 문제보다 쉬운 문제...

문제를 설명하자면, n 개의 물건과 그 가격들을 입력받습니다. 이후 가게 주인은 n 개의 가격들을 동일하게 조절하고 싶어 합니다.(왜???)

그리고 기존(old) 가격과 새로 고친(new) 가격의 차이가 k 보다 작거나 같도록 해야 합니다.

결과는 n개의 물건들의 가격을 동일하게 고칠 수 있다면 그 가격(B)의 maximum을, 고칠 수 없다면 -1을 출력하는 것입니다.

저는 예시들을 보고 한 가지 규칙을 발견했는데 n 개의 물품 중 가장 최소 가격의 +k 보다 더 커질 수는 없다는 것이었습니다.

즉 최소 기존 가격을 찾고 이후 k를 더해서 새 가격 B를 만든 후에 다시 전체 가격과 비교해 모든 가격들이 B와 차이가 k와 작거나 같다면 고칠 수 있는 것으로 판단했습니다.

그대로 코드로 옮겼고, 맞았습니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>

int num[102];

int main() {
    int q;int n, k;
    scanf("%d", &q);
    
    while(q--) {
        int min = 1e+9;
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; ++i) {
            scanf("%d", num + i);
            if(num[i] < min) min = num[i];
        }
        
        int newPrice = min + k;
        for(int i = 0; i < n; ++i)
            if(abs(newPrice - num[i]) > k) {
                newPrice = -1;
                break;
            }
            
        printf("%d\n", newPrice);
    }
}

D. Candy Box (easy version)

문제의 시간 조건을 보자마자 "3초" 라길래 잠시 멈칫했습니다. 넉넉한 시간을 주는 거보니 검사할게 많나 싶었죠..ㅎㅎ

문제를 다 읽고 나서 뭔 소리지 싶었습니다. 계속 읽고 이해하다 보니 Candy의 Type마다 각각 다른 개수를 선택하라는 얘기였죠.

그래서 n 개의 Type을 입력받고 각각의 개수를 세는 Array를 만들었습니다.

그리고 Candy의 Maximum 개수를 세라길래 큰 것부터 고르려 내림차순 정렬했습니다.

하지만 문제를 풀다 보니 같은 수가 연달아 나올 때는 어떻게 해야 하느냐 가 관건이었습니다. 이를 처리하느라 시간을 좀 써서 코드를 제출하긴 했는데 결국 2번째 case에서 틀리더군요..

아무튼 코드를 보여드리면 이렇습니다. (틀린 코드입니다!!)

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 200002
using namespace std;

bool cmp(const int &a, const int &b) {
	return a > b;
}

int main() {
	int q;
	scanf("%d", &q);

	while (q--) {
		int type[MAX] = {}; // type array represents the number of types of candies
		int n, tmp;
		scanf("%d", &n);

		for (int i = 0; i < n; ++i) {
			scanf("%d", &tmp);
			++type[tmp];
		}

		sort(type, type + MAX, cmp);

		int maxi = type[0], cnt = maxi;
		for (int i = 1; i < MAX; ++i) {
			if (maxi == 1 || maxi == 0) break;

			if (type[i] == type[i-1])
				cnt += --maxi;
			else {
				cnt += type[i];
				maxi = type[i];
			}
		}

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

테스트가 끝나고 고수들 코드를 보니 엄청 간단히 풀었더군요.... ㅠㅠ

아직 수련이 더욱 필요하다는 것을 깨달았습니다.

C번 문제는 어떻게 풀지 거의 마지막의 마지막에 가서야 알고리즘이 떠올라서 풀던 도중에 시간이 끝나 제출하지는 못했습니다ㅠㅠ

나중에 다시 풀어보기로 했고, 이렇게 2시간을 다 써서 "8 문제 중 2 Accepted, 1 Wrong" 이라는 아쉬움이 매우매우매우 많이 남는 첫 Contest 였습니다.

시간이 남는다면 틀린 문제와 나머지 문제들을 풀고 싶다는 생각이 들었습니다.

~~레이팅 점수나 잘 나오면 좋겠는데...~~

글 잘 보시고 틀린 점이나 개선점, 말하고 싶은 점이 있으시다면 얼마든지 댓글 달아주세요!!

티스토리툴바