[선데이코딩] 선데이 코딩 베타 라운드 1 이야기

백준 사이트에도 드디어 한국형 코드포스가 생겼다.

선데이 코딩이라는 곳인데 BOJ에서 직접 운영한다. https://www.sundaycoding.xyz/

17년 5월 31일은 베타 라운드 1이 열리는 날이었고 문제를 풀어보았다.(저녁 7시~10시까지 3시간 진행이었다.)

어짜피 랭크가 베타버전이 끝나면 없어지긴 하지만 오늘은 7문제중 3문제를 풀어

기본 레이팅에서 +26인 1526점을 받아 gold 랭크가 됐다.

문제는 전반적으로 백준 사이트 답게 나온 것 같다.

A번은 출력, B번은 그리디 알고리즘, C번은 DP, D번은 백트래킹, E번은 세그먼트 트리, F번은 DP(인지는 잘 모르겠다.) G번은 기하이다.

사실 A, B, C, D, E, F, G 모두 BOJ에서 자주 다루는 문제이다.

A번은 [2557번] Hello World :: https://www.acmicpc.net/problem/2557 와 동일하고

B번은 [2294번] 동전 2 :: http://www.crocus.co.kr/638 와 동일하지만 쉽게 냈고(DP에서 Greedy로 변형)

C번은 [11058번] 크리보드 :: https://www.acmicpc.net/problem/11058 문제이고

D번은 백트래킹 알고리즘을 이용하면 구현이 가능하다고 들었다.(스터디원이 푸셔서 알고리즘 분류를 들었습니다.)

E번은 [10868번] 최소값 :: http://www.crocus.co.kr/751 문제를 update만 구현하면 되고

F번은 [10942번] 팰린드롬? :: http://www.crocus.co.kr/676 에서 N제한이 늘어난 문제이다.

G번은 고등학교 3학년때 배운 3차원 상의 점과 직선사이의 거리를 구하는 기하 문제이다.

우선 G번을 못푼게 너무 아쉽고 C번은 DP인지 예상도 못했다.

F번은 문제를 풀어본 기억이 있으나 N제한이 바뀌니 접근하기가 어려웠다.

D번은 다른 문제를 푸느라 넘겼던 문제이다.

푼 문제들에 대해서만 이야기를 해보려 한다.

A. 헬로 월드 :: https://www.sundaycoding.xyz/contest/1/problem/1

생략

B. 동전 교환 :: https://www.sundaycoding.xyz/contest/1/problem/2

이 문제는 원래 DP로 풀 수 있다. 하지만 K 범위가 상당히 크기에 DP로 접근하기에는 배열 크기가 메모리 제한을 넘어서기에 불가능하다.

이 문제는 자세히 보면 Ai는 Ai-1의 배수라고 되어있다.

따라서 이 문제는 그리디로 해결할 수 있게 된다.(들은 내용이라 정확한 증명은 잘 모르겠다..)

결국 DP로 해결하지 않고 그리디로 해결 할 수 있는 문제가 되고 코드는 아래와 같다.

시간 복잡도는 O(n)이다.

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

#include <iostream> #include <cstdio>   using namespace std;   int main() {     int n, m;     scanf("%d %d", &n, &m);       int coin[20];     for (int i = 0; i < n; i++)         scanf("%d", &coin[i]);       int cnt = 0;     for(int i = n-1; i >= 0; i --)         if (m - coin[i] >= 0)         {             m -= coin[i];             cnt++;             i++;         }     printf("%d", cnt);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

E. 수열과 최소값 :: https://www.sundaycoding.xyz/contest/1/problem/5 

가장 기본적인 세그먼트 트리 문제이다.

세그먼트 트리 개념 :: http://www.crocus.co.kr/648

쿼리가 주어지기에 그냥 돌리면 당연히 TLE가 나게 되고 세그먼트 트리를 이용하여 해결한다.

update 부분은 해당하는 노드 구간에서의 최솟값을 계속해서 return해줘서 update해주면 된다.

시간 복잡도는 O(mlgn)이다.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
 
#define INF 987654321
using namespace std;
 
int init(vector<int> &arr, vector<int> &tree, int node, int start, int end)
{
    if (start == end)
        return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
 
    return tree[node] = min(init(arr, tree, node * 2, start, mid), init(arr, tree, node * 2 + 1, mid + 1, end));
}
 
int update(vector<int> &tree, int node, int start, int end, int index, int diff)
{
    if (!(start <= index && index <= end))
        return tree[node];
    
    if (start == end)
        return tree[node] = diff;
 
    if (start != end)
    {
        int mid = (start + end) / 2;
        return tree[node] = min(update(tree, node * 2, start, mid, index, diff), update(tree, node * 2 + 1, mid + 1, end, index, diff));    
    }
 
}
 
int query(vector<int> &tree, int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return INF;
 
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
 
    return min(query(tree, node * 2, start, mid, left, right), query(tree, node * 2 + 1, mid + 1, end, left, right));
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (1 + h));
 
    vector<int> arr(n);
    vector<int> tree(tree_size);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    init(arr, tree, 1, 0, n - 1);
 
    int m;
    scanf("%d", &m);
 
    while (m--)
    {
        int num;
        scanf("%d", &num);
 
        if (num == 1)
        {
            int idx, val;
            scanf("%d %d", &idx, &val);
 
            int diff = val;
            arr[idx - 1] = val;
 
            update(tree, 1, 0, n - 1, idx - 1, diff);
        }
        
        else if(num == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
 
            int ans = query(tree, 1, 0, n - 1, left - 1, right - 1);
            printf("%d\n", ans);
        }
    }
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>