이소영

import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; public class Solution { // 카펫 public static void main(String[] args) throws NumberFormatException, IOException { // int brown = 10; // int yellow = 2; // int brown = 8; // int yellow = 1; int brown = 24; int yellow = 24; Solution main = new Solution(); System.out.println(Arrays.toString(main.solution(brown, yellow))); } static class Info { int height; int width; public Info(int height, int width) { this.height = height; this.width = width; } } private static int[] solution(int brown, int yellow) { int[] answer = new int[2]; ArrayList<Info> info = new ArrayList<>(); int yh = 1; int yw = yellow/yh; while(yh <= yw) { info.add(new Info(yh, yw)); yh += 1; yw = yellow/yh; } // for (Info i : info) { // System.out.println(i.height + ", " + i.width); // } for (int i = 0; i < info.size(); i++) { if((info.get(i).width + 2)*2 + info.get(i).height*2 == brown) { answer[0] = info.get(i).width+2; answer[1] = info.get(i).height+2; } } // System.out.println(Arrays.toString(answer)); return answer; } }

public class Solution { // 피로도 public static void main(String[] args) { // int k = 80; // int[][] dungeons = { { 80, 20 }, { 50, 40 }, { 30, 10 } }; // int k = 30; // int[][] dungeons = { { 20, 20 }, { 50, 40 }, { 30, 10 } }; // int k = 40; // int[][] dungeons = { { 40, 20 }, { 10, 10 }, { 10, 10 }, { 10, 10 }, { 10, 10 } }; int k = 5000; int[][] dungeons = { { 1000, 1000 }, { 1000, 800 } ,{ 900, 900 }, {1500, 1500}, { 200, 40 }, { 1500, 1000 }}; Solution main = new Solution(); System.out.println(main.solution(k, dungeons)); } private int solution(int k, int[][] dungeons) { // DFS 실행하기 dfs(dungeons, new boolean[dungeons.length], k, 0); return max; } static int max = -1; // 최대 개수 담기 private void dfs(int[][] dungeons, boolean[] v, int k, int cnt) { for (int i = 0; i < dungeons.length; i++) { if (v[i]) continue; // 이미 탐험한 던전이라면 continue; // 방문하지 않은 던전 탐험 if(k >= dungeons[i][0]) { // System.out.println(i + "던전 탐험"); v[i] = true; // 던전 탐험 DFS(dungeons, v, k - dungeons[i][1], cnt + 1); // System.out.println(i + "던전 탐험 취소"); v[i] = false; // 탐험했던 던전 취소 } } max = Math.max(max, cnt); return; } }

import java.util.LinkedList; import java.util.Queue; public class Solution{ // 전력망을 둘로 나누기 public static void main(String[] args) { int n = 9; int[][] wires = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 7, 8 }, { 7, 9 } }; // int n = 4; // int[][] wires = {{1, 2}, {2, 3}, {3, 4}}; // int n = 7; // int[][] wires = {{1, 2}, {2, 7}, {3, 7}, {3, 4}, {4, 5}, {6, 7}}; Solution main = new Solution(); System.out.println(main.solution(n, wires)); } private int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; int[][] adj = new int[n+1][n+1]; // 인덱스는 0부터 시작, 송전탑은 1부터 시작하므로 인접행렬 길이 +1 for (int i = 0; i < wires.length; i++) { adj[wires[i][0]][wires[i][1]] = adj[wires[i][1]][wires[i][0]] = 1; // 양방향 } // 하나씩 끊어보기 for (int i = 0; i < wires.length; i++) { int sNode = wires[i][0]; int eNode = wires[i][1]; // 연결된 송전탑 끊기 adj[sNode][eNode] = 0; adj[eNode][sNode] = 0; answer = Math.min(answer, bfs(adj, new boolean[n+1], 1, n)); // 끊었던 송전탑 연결 adj[sNode][eNode] = 1; adj[eNode][sNode] = 1; } return answer; } private int bfs(int[][] adj, boolean[] v, int sNode, int n) { Queue<Integer> q = new LinkedList<>(); q.offer(sNode); int cnt = 1; // 개수 1 더하기(1번 송전탑) while(!q.isEmpty()) { int node = q.poll(); v[node] = true; for (int i = 1; i < v.length; i++) { if(!v[i] && adj[node][i] == 1) { q.offer(i); cnt++; } } } return (int)Math.abs(cnt - (n - cnt)); } }

public class Solution{ // 전력망을 둘로 나누기 public static void main(String[] args) { // int n = 9; // int[][] wires = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 7, 8 }, { 7, 9 } }; // int n = 4; // int[][] wires = {{1, 2}, {2, 3}, {3, 4}}; int n = 7; int[][] wires = {{1, 2}, {2, 7}, {3, 7}, {3, 4}, {4, 5}, {6, 7}}; Solution main = new Solution(); System.out.println(main.solution(n, wires)); } private int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; int[][] adj = new int[n+1][n+1]; // 인덱스는 0부터 시작, 송전탑은 1부터 시작하므로 인접행렬 길이 +1 for (int i = 0; i < wires.length; i++) { adj[wires[i][0]][wires[i][1]] = adj[wires[i][1]][wires[i][0]] = 1; // 양방향 } // 하나씩 끊어보기 for (int i = 0; i < wires.length; i++) { int sNode = wires[i][0]; int eNode = wires[i][1]; // 연결된 송전탑 끊기 adj[sNode][eNode] = 0; adj[eNode][sNode] = 0; // answer = Math.min(answer, bfs(adj, new boolean[n+1], 1, n)); int nodeCnt = dfs(adj, new boolean[n+1], 1); answer = Math.min(answer, (int)Math.abs(nodeCnt-(n-nodeCnt))); // 끊었던 송전탑 연결 adj[sNode][eNode] = 1; adj[eNode][sNode] = 1; } return answer; } private int dfs(int[][] adj, boolean[] v, int sNode) { int cnt = 1; // 현재 송전탑 v[sNode] = true; for (int i = 0; i < adj.length; i++) { if(!v[i] && adj[sNode][i] == 1) { cnt += dfs(adj, v, i); } } // System.out.println(Arrays.toString(v)); // System.out.println(cnt); return cnt; } }