구름톤 챌린지: 3주차(230828~230829)

230828

Day11 문제풀이

코드

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

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

        int N = Integer.parseInt(br.readLine());
        String[] split = br.readLine().split(" ");
        int A = Math.max(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
        int B = Math.min(Integer.parseInt(split[0]), Integer.parseInt(split[1]));

        int count = Integer.MAX_VALUE;
        for(int i=N/A; i>=0; i--) {
            if((N - i*A) % B != 0) continue;

            for(int j=0; j<N/B+1; j++) {
                if(i * A + j * B == N) {
                    System.out.print(i+j);
                    return;
                }
            }
        }
        System.out.print(-1);
    }
}

중요

• 이번 풀이의 중심은 시간초과를 잡는 것이었다. 아이템의 개수를 최소화하기 위해선 치유력이 높은 것을 많이 사용하고, 남은 부분을 치유력이 비교적 낮은 것으로 채워넣어야 한다.
  치유력이 높은 것을 A, 치유력이 낮은 것을 B라고 가정하였을 때, for문에서 A는 최댓값부터 시작하는 것이 중요하다.

230829

Day12 문제풀이

코드

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

class Main {
    static boolean[] visit;
    static boolean[][] house;
    static Queue<Integer> queue = new LinkedList<>();
    static int N;
    static int[][] neighbor = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

        N = Integer.parseInt(br.readLine());

        visit = new boolean[N*N];
        house = new boolean[N][N];
        for(int i=0; i<N; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                if(Integer.parseInt(tk.nextToken()) == 1) house[i][j] = true;
            }
        }

        int count = 0;
        for(int i=0; i<N*N; i++) {
            if(!house[i/N][i%N]) continue;
            if(bfs(i)) count++;
        }

        System.out.print(count);
    }

    public static boolean bfs(int R) {
        if(visit[R]) return false; // 처음부터 이미 visit인 경우 -> 이미 전기 공급 받음
        visit[R] = true;
        queue.offer(R);

        while(!queue.isEmpty()) {
            int u = queue.poll();
            int i = u/N;
            int j = u%N;

            for(int k=0; k<neighbor.length; k++) {
                try {
                    int v = (i + neighbor[k][0]) * N + (j + neighbor[k][1]);
                    if(!visit[v] && house[i + neighbor[k][0]][j + neighbor[k][1]]) {
                        visit[v] = true;
                        if(!queue.contains(v)) queue.offer(v);
                    }
                } catch(Exception e) {}
            }
        }

        return true;
    }
}

중요

• 이번 문제는 메모리 관리가 핵심이었다. 계속 메모리초과로 인해 런타임에러가 발생했는데, 인접리스트가 문제였다.
  인접리스트를 없애고 매번 이웃을 찾아주었더니 메모리초과 문제를 해결할 수 있었다.
  인접리스트를 미리 만들어두는 편이 훨씬 보기 좋다고 생각하였는데(재사용성 또한..), 메모리초과 문제도 생각해봐야 한다는 것을 알게 되었다.