구름톤 챌린지: 3주차(230830~230901)

230830

Day13 문제풀이

코드

import java.io.*;
import java.util.*;

class Main {
    static int[][] building;
    static boolean[] visit;
    static int N;

    static Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        building = new int[N][N];
        for(int i=0; i<N; i++) {
            tk = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                building[i][j] = Integer.parseInt(tk.nextToken());
            }
        }

        visit = new boolean[N*N];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<N*N; i++) {
            int count = bfs(i);
            if(count < K) continue;

            if(map.containsKey(building[i/N][i%N])) map.put(building[i/N][i%N], map.get(building[i/N][i%N]) + 1);
            else map.put(building[i/N][i%N], 1);
        }

        int maxKey = 0, maxCount = 0;
        for(int key : map.keySet()) {
            if(maxCount < map.get(key) || (maxCount == map.get(key) && maxKey < key)) {
                maxKey = key;
                maxCount = map.get(key);
            }
        }
        System.out.print(maxKey);
    }

    public static int bfs(int R) {
        int count = 0;

        if(visit[R]) return count;
        visit[R] = true;
        count++;

        int[][] list = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        queue.offer(R);

        while(!queue.isEmpty()) {
            int u = queue.poll();

            for(int i=0; i<list.length; i++) {
                int v = (u/N + list[i][0]) * N + (u%N + list[i][1]);
                try {
                    if(visit[v] || building[u/N][u%N] != building[u/N + list[i][0]][u%N + list[i][1]]) continue;

                    count++;
                    visit[v] = true;
                    queue.offer(v);
                } catch(Exception e) {} // 인덱스 범위 초과
            }
        }

        return count;
    }
}

중요

• 최대 단지수가 같을 경우 유형 번호가 더 큰 쪽을 우선한다는 조건을 빠뜨려 한 번 fail이 떴었다. 문제를 파악하는 것도 중요하지만, 조건 하나하나도 모두 읽고 문제를 풀이하는 습관을 들여야겠다.
• 근접리스트를 {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}가 아닌 {-1*N, N, -1, 1}로 두었을 경우 인덱스 범위에서 벗어나는 경우를 잡을 수 없으니 주의해야 한다.

230831

Day14 문제풀이

코드

import java.io.*;
import java.util.*;

class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] visited;
    static int count = 0;

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

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());
        int K = Integer.parseInt(tk.nextToken());

        visited = new int[N];

        for(int i=0; i<N; i++) graph.add(new ArrayList<Integer>());
        for(int i=0; i<M; i++) {
            tk = new StringTokenizer(br.readLine(), " ");

            int u = Integer.parseInt(tk.nextToken()) - 1;
            int v = Integer.parseInt(tk.nextToken()) - 1;

            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        for(int i=0; i<N; i++) Collections.sort(graph.get(i));

        dfs(K - 1);

        int countNode = 0;
        int maxIndex = 0;
        int maxCount = 0;

        for(int i=0; i<visited.length; i++) {
            if(visited[i] == 0) continue;
            countNode++;
            if(maxCount < visited[i]) {
                maxCount = visited[i];
                maxIndex = i;
            }
        }

        System.out.print(countNode + " " + (maxIndex+1));
    }

    public static void dfs(int R) {
        visited[R] = ++count;

        for(int v : graph.get(R)) {
            if(visited[v] == 0) {
                dfs(v);
                break;
            }
        }
    }
}

중요

• 이 문제의 핵심은 각 노드에서 갈 수 있는 노드 중 최솟값의 노드로만 이동한다는 것이다.
  기존 dfs랑 비슷하지만 처음으로 갈 수 있는 노드로 이동 후 다른 노드로 뻗어가지 않도록 break로 중간에 반복을 끊어주는 것이 중요하다.

230901

Day15 문제풀이

코드

import java.io.*;
import java.util.*;

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

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        int K = Integer.parseInt(tk.nextToken());

        int[][] Cs = new int[N][2]; // P C
        for(int i=0; i<N; i++) {
            tk = new StringTokenizer(br.readLine(), " ");

            Cs[i][0] = Integer.parseInt(tk.nextToken());
            Cs[i][1] = Integer.parseInt(tk.nextToken());
        }

        Arrays.sort(Cs, (o1, o2) -> {
            if(o2[1]/o2[0] == o1[1]/o1[0]) return o1[0] - o2[0];
            else return o2[1]/o2[0] - o1[1]/o1[0];
        });

        long result = 0;
        for(int i=0; i<Cs.length; i++) {
            // 하나 사기
            if(Cs[i][0] <= K) {
                result += Cs[i][1];
                K -= Cs[i][0];
            }
            // 나누어 사기
            else {
                int CP = Cs[i][1] / Cs[i][0];
                result += (K * CP);
                K -= K;
            }
            if(K == 0) break;
        }

        System.out.print(result);
    }
}

중요

• 최대 포만감을 위해선 Ci / Pi 값이 큰 값부터 구매하는 것이 포인트이다. 이를 위해 Ci/Pi 값을 기준으로 배열을 정렬해주었다.