[대회] 아레나

아레나 개요 : https://www.acmicpc.net/board/view/121439
아레나 자세한 사항 : https://solved.ac/arena/propose

요즘 백준에서 개최되는 대회는 시간만 맞으면 웬만해선 참석중이었으며,
때마침 백준의 티어를 볼 수 있는 solved.ac에서 대회를 개최하였습니다.

바쁘지만, 재밌어 보였기에 빠질 수 없었습니다...

퍼포먼스 기준 278위이나, 사실상 200등 언저리까지 갔었습니다 !
뽀록이겠죠,,,ㅎㅎ
이번 대회는 800명 정도 가량 출전했던 것 같습니다.

아직은 허접한 실력이네요..
골드 티어 정도 오니까 시간 내에 풀기가 어려운 것 같아요..
어떻게 접근하는 지는 알고, 구현은 할 수 있지만 자꾸 시간초과가 떠서 이것을 해결하기 위해선 근본적으로 시간복잡도를 줄여야 할텐데... --> 이를 위해 요즘 알고리즘 공부를 별도로 진행하는데도 어려움이 있네요.

대회당시 저 빼고 다른 분들은 너무 빠르게 후다닥 푸시길래 당황했습니다.
다른 분들은 A -> B -> H -> E -> G -> I 순으로 푸시며 후다닥 치고 나가셨습니다.
저또한 위와 같은 순서로 치고나갔습니다.
H 까진 나름 할만??? 했습니다. But E의 시간복잡도를 줄여야만 했습니다.
시간초과만 10번을 경험했습니다..

1트엔 접근 방법을 몰라서 도전중에 틀렸으나, 다음 부터는 접근방법을 찾게되어 (해쉬맵, 스택, dfs로 하되 좀더 빠르게 돌아가도록) 구현했습니다.
그러나 시간초과 몇 번뜨다보니, 이 방법은 아닌 것 같아 다른 알고리즘으로 구현해보았습니다. 그리디로 풀다 안되었습니다.
이때, 필자는 결정했습니다. dp로 풀기로 결심했습니다.
이에, dp로 점화식을 세우는데 시간을 소요하고, 많은 도전을 했으나 저를 기다리는 것은 메모리초과와 시간초과 뿐이었습니다.
중간에 속도가 제일 빠른 언어이며 저에겐 보조언어인 C++로 한 번 풀어봤는데, 역시나 구현하는 스킬이 부족하여 틀리게 되었습니다.

서론이 너무 길었네요 문제 및 코드작성하겠습니다.

A - 양말 짝 맞추기

https://www.acmicpc.net/problem/28431

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Integer> socks = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            int sockNumber = Integer.parseInt(br.readLine());
            socks.put(sockNumber, socks.getOrDefault(sockNumber, 0) + 1);
        }
        int remainingSock = -1;
        for (Map.Entry<Integer, Integer> entry : socks.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                remainingSock = entry.getKey();
                break;
            }
        }
        System.out.print(remainingSock);
    }
}

B - 끝말잇기

https://www.acmicpc.net/problem/28432

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] endWords = new String[n];
        for (int i = 0; i < n; i++) {
            endWords[i] = br.readLine();
        }
        int m = Integer.parseInt(br.readLine());
        String[] candidates = new String[m];
        for (int i = 0; i < m; i++) {
            candidates[i] = br.readLine();
        }
        String answer = "";
        for (String candidate : candidates) {
            boolean isValidCandidate = true;
            Set<String> usedWords = new HashSet<>();
            for (int index = 0; index < n; index++) {
                String currentWord;
                if (endWords[index].equals("?")) {
                    currentWord = candidate;
                } else {
                    currentWord = endWords[index];
                }
                if (usedWords.contains(currentWord)) {
                    isValidCandidate = false;
                    break;
                }
                usedWords.add(currentWord);
                if (index == n - 1) {
                    break;
                }
                if (endWords[index + 1].equals("?")) {
                    if (!currentWord.endsWith(candidate.substring(0, 1))) {
                        isValidCandidate = false;
                        break;
                    }
                } else if (!currentWord.endsWith(Character.toString(endWords[index + 1].charAt(0)))) {
                    isValidCandidate = false;
                    break;
                }
            }
            if (isValidCandidate) {
                answer = candidate;
                break;
            }
        }
        System.out.print(answer);
    }
}

H- 행렬 연산 (행렬 계산하기)

https://www.acmicpc.net/problem/28438

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        int[] rowAdd = new int[N];
        int[] colAdd = new int[M];

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int index = Integer.parseInt(st.nextToken()) - 1;
            int value = Integer.parseInt(st.nextToken());

            if (operation == 1) {
                rowAdd[index] += value;
            } else {
                colAdd[index] += value;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int cellValue = rowAdd[i] + colAdd[j];
                System.out.print(cellValue + " ");
            }
            System.out.println();
        }
    }
}

E - 배수피하기 _ 시간초과 --> 해결함

https://www.acmicpc.net/problem/28435

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] c = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(st.nextToken());
            c[a % K]++;
        }

        long ans = 1;
        for (int i = 1; i < (K + 1) / 2; i++) {
            long pi = powMod(2, c[i], MOD);
            long pj = powMod(2, c[K - i], MOD);
            ans = (ans * (pi + pj - 1)) % MOD;
        }
        ans = (ans * (c[0] + 1)) % MOD;

        if (K % 2 == 0) {
            ans = (ans * (c[K / 2] + 1)) % MOD;
        }

        ans = (ans + MOD - (N + 1)) % MOD;
        System.out.println(ans);
    }

    private static long powMod(long base, int exponent, int mod) {
        long result = 1;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent >>= 1;
        }
        return result;
    }
}

또는

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] c = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(st.nextToken());
            c[a % K]++;
        }

        long ans = 1;
        for (int i = 1; i < (K + 1) / 2; i++) {
            long pi = 1, pj = 1;
            for (int k = 0; k < c[i]; k++) {
                pi = pi * 2 % MOD;
            }
            for (int k = 0; k < c[K - i]; k++) {
                pj = pj * 2 % MOD;
            }
            ans = (ans * (pi + pj - 1)) % MOD;
        }
        ans = (ans * (c[0] + 1)) % MOD;

        if (K % 2 == 0) {
            ans = (ans * (c[K / 2] + 1)) % MOD;
        }

        ans = (ans + MOD - (N + 1)) % MOD;
        System.out.println(ans);
    }
}

G - 막대 만들기 (틀림)