2019 ACM ICPC Seoul Regional 예선 참가 후기 및 문제 풀이

2019 ICPC Seoul Regional

ACM-ICPC는 알고리즘에 자신 있는 사람이라면 한번쯤 도전해볼 만한 세계 규모의 프로그래밍 경진 대회이다.

나는 이번 여름 방학부터 본격적으로 알고리즘 문제를 풀었기에 아직 많이 부족하지만 내년을 기대하면서 Negend(Next Legend)라는 이름으로 (최)진혁이와 예준이와 예선 대회에 참가했다.

운 좋게도 4문제 풀고도 학교에서는 좋은 성적을 거둘 수 있었다.

이 포스팅을 통해 대회 후기와 우리가 접근한 문제들의 접근법과 코드를 공유하고자 한다.

대회 준비

대회에 앞서서 같이 풀어본 경험이 많이 부족하기 때문에 한 대의 컴퓨터로 2018년도, 2017년도 문제를 함께 푸는 연습 세션을 진행했다.

처음 세션을 진행했을 때는 문제를 어떻게 같이 푸는지 모르겠어서 나한테 주어진 문제는 혼자 풀려고 애를 많이 썼다. 하지만 내가 마지막에 풀려는 문제를 풀지 못한 체 세션을 끝내게 되었다.

2번째 세션부터 진혁이와 예준이와 알고리즘 방법에 대해서 의논하기로 맘 먹었다. 각자 접해본 문제와 방법이 다르기 같이 풀 때 더 큰 효과가 있을 수 있다 판단했기 때문이다.

실제로 진혁이와 예준이와 의논하면서 문제 풀이 방법까지 접근하는 시간이 훨씬 짧아짐을 느꼈다.

뿐만 아니라 모니터와 키보드를 하나 더 준비해서 실제 환경과 유사하게 문제를 풀어본 경험이 도움이 많이 됐다.

대회 당일

막상 대회장에 도착하니 긴장이 밀려왔다.

내년을 목표로 경험삼아 나온 이번 대회지만 그래도 잘하고 싶은 욕심이 컸다.

그래도 진혁이랑 예준이가 옆에서 많이 힘이 되어주어서 조금 긴장을 덜고 힘내볼 수 있었다.

ICPC 서버의 문제로 등록을 제외하고는 제출의 결과를 확인 받지 못했다.

제출의 결과를 받지 못하니 중간부터 답답함과 함께 집중력이 흐트러지기 시작했다.

이때가 진짜 고비였다.(진혁, 예준이가 버텨줘서 진짜 고마웠다.)

추가 시간 30분 포함해서 3시간 반 동안에 시험 동안에 우리는 총 6문제에 솔루션 제출하고 시험을 마무리했다.

우여곡절 끝에 끝냈지만 만족했다.

대회 후기

대회 환경에 문제가 생기는 바람에 심적으로 너무 힘들었다.

L번과 J번을 틀린 이유를 확인하지 못한 채로 시험을 마무리하게 되어서 너무 아쉬움이 남는다.

알고리즘을 떠올리고 이를 증명해내지 못해서 엄한 시간을 너무 많이 낭비해버렸다. 이를 더 공부해봐야겠다.

이번 대회를 통해서 같이 하는 즐거움을 조금은 느낀 것 같아 너무 감사하다. 진짜 진혁, 예준에게 감사하다.

내년에는 진짜 레전드가 되도록 열시미 해봐야겠다!

문제 풀이

문제는 우리가 쉽게 접근했던 문제 순으로 나열했다.

Problem B (Balanced String)

백준 17520번 링크

이 문제는 디피로 접근하면 쉽게 풀 수 있는 문제이다.

이진 문자열의 모든 부분 문자열이 균형잡힌 문자열이기 때문에

1자리부터 시작해서 원하는 자리까지 0과 1의 개수차가 0과 1인 애들 정보를 계속해서 기억해주면 되는 문제이다.

#include <cstdio>
int n, c0, c1, n0, n1;
int main(){
    c1 = 2;
    scanf("%d", &n);
    for(int i = 1; i < n; i++)n1 = (c0 * 2) % 16769023, n0 = c1, c0 = n0, c1 = n1;
    printf("%d", (c0 + c1) % 16769023);
}

Problem H (Four Squares)

백준 1699번 링크

이 문제는 이전에 풀어본 백준 1699번과 거의 동일하다.(오늘 백준 사이트에 올라온 것을 보고서야 알았다…)

이 문제도 DP로 접근하면 쉽게 풀 수 있는 문제이다.

일단 num에 원하는 값보다 작거나 같은 모든 제곱수를 저장하고 1부터 n까지 값들을 찾아나간다.

이때 해당 수에서 제곱수를 뺀 위치에 값이 있을 경우 중 제일 작은 값에다가 +1을 해주어 해당 위치에 저장한다.

#include <cstdio>

int n, m, arr[100001], num[100001];

int main(){
    scanf("%d", &n);
    for(int i = 1; i < 100001; i++){
        //일단 해당 수 전의 모든 제곱수들을 다 저장해줌
        int sqr = i*i;
        if(sqr > n)break;
        num[i] = sqr, m = i + 1;
    } 
    for(int i = 1; i <= n; i++){
        int MIN = 1000000;
        //i에서 제곱수들을 뺀 위치에 값이 있는 애들 중에 제일 작은 값 + 1을 넣어줌
        for(int j = 0; j < m; j++){
            if(i - num[j] < 0) continue;
            if((i - num[j]) && !arr[i - num[j]])continue;
            if(arr[i - num[j]] + 1 < MIN) MIN = arr[i - num[j]] + 1;
        }
        arr[i] = MIN;
    }
    printf("%d", arr[n]);
}

Problem C (Byte Coin)

백준 17521번 링크

이 문제는 그냥 말그대로 제일 쌀 때 사서 제일 비쌀 때 팔면 되는 문제이다.

타입을 조심해주는게 관건이다!

#include <cstdio>
int n, cur, d = -1, arr[16];
int main(){
    long long ans = 0, c = 0, coin = 0;
    scanf("%d %lld", &n, &c);
    for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
    for(int i = 1; i <= n; i++){
        cur = arr[i] - arr[i-1];
        if(cur != 0)cur = cur > 0 ? 1 : -1;
        if(d == cur || cur == 0)continue;
        if(d > 0)c += coin * arr[i-1], coin = 0;
        else coin = c / arr[i-1], c -= coin * arr[i-1];
        if(c > ans)ans = c;
        d = cur;
    }
    if(c + coin * arr[n - 1] > ans)ans = c + coin * arr[n - 1];
    printf("%lld", ans);
}

Problem L (Two Machines)

백준 17528번 링크

11월 4일, 한달만에 드디어 Two Machines를 풀어냈다…

이분탐색, dp, 그리디 다 해보고 결국에 이정진님의 댓글을 보고 dp를 이용해서 문제를 풀어내게 되었다.

작업의 개수는 250개로 각 작업의 최대값은 250이기 때문에 최대 시간은 62500이다.

이 때 250개의 작업쌍을 받게 될 때 마다 62500의 경우를 확인한다면 이때 총 시간은 62500*250으로 천오백만이된다. 1초가 1억이라고 봤을 때 이거는 될 방법이라고 봤다.

방법은 어레이 dp[251][62501] 짜리를 하나 준비한다.

dp[i][j]는 i번째 작업이면서 a가 j일 때, b가 가질 수 있는 최소값을 의미한다.

dp[i][j]는 dp[i-1][j]에서 $a_i$와 $b_i$ 중 하나를 선택해서 더해주며 업데이트된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, arr[251][2], dp[251][62501];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d %d", &arr[i][0], &arr[i][1]);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 62501; j++)dp[i][j] = 987654321;
    }
    dp[0][arr[0][0]] = 0;
    dp[0][0] = arr[0][1];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 62501; j++){
            if(dp[i - 1][j] == -1)continue;
            dp[i][j + arr[i][0]] = min(dp[i][j + arr[i][0]], dp[i - 1][j]);
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + arr[i][1]); 
        }
    }
    int ans = 987654321;
    for(int i = 0; i < 62501; i++)ans = min(ans, max(i, dp[n - 1][i]));
    printf("%d", ans);
}

대회를 마치며

ACM-ICPC라는 큰 대회에서 입상도 입상이지만 팀으로 함께 하는 기쁨을 느낄 수 있어서 정말 좋았다.

그리고 문제 접근을 잘못하는 오류를 줄이기 위해 내 알고리즘을 증명해낼 수 있는 능력을 기르거나 더 넓은 시야를 길러야 겠다!