코딩테스트/[백준] 코딩테스트 연습

독서실 거리두기 - 20665번

풀이 방법 그냥 차근차근 구현을 통해 풀이했다. 먼저 입력받은 시간을 분으로 변경해서 배열에 저장했다. 정렬을 통해 순서를 정해주고 우선순위 큐를 통해 꺼내는 순서를 정해주었다. 큐에 넣고 꺼낼 때마다 가장 멀리 있는 좌석을 선택해서 관리자가 들어갈 수 있는지 확인해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, T, P; static int[][] arr; static int[] seat; static PriorityQueue pq = new PriorityQueue(); public static void main(String[] args) throws IOExcept..

뱀과 사디리 게임 - 16928번

풀이 방법 bfs를 이용해서 최단 경로를 구해주었다. 현재 위치와 위치에 도달하기까지 굴린 주사위 횟수를 가진 클래스를 만들어 주었다. map에는 뱀과 사다리 경로를 넣어주었는데 굳이 따로 나눌 필요없이 한번에 넣어주었다. 판의 크기가 100으로 고정된것이 아니기 때문에 배열을 이용해서 boolean을 체크해서 방문된 곳을 확인하는 것보다는 set을 이용해서 방문했던 위치를 확인해 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..

택배 - 1719번

풀이 방법 모든 최단 경로를 구할 수 있는 플로이드 와샬 방법으로 풀이 했다. 처음 지나는 경로를 찾는 것보다 마지막 지나는 경로를 찾는 것이 수월하다고 판단되어 맨 처음 지나가는 경로를 구하는 것이 아닌 마지막 경로를 구해서 출력할 때 반대로 뒤집는 방법을 사용했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri..

점수따먹기 - 1749번

풀이 방법 배열의 누적합을 이용해서 나타내고 가능한 모든 분을 비교하며 풀어주었다. 내 코드 package com.company; import java.io.*; import java.util.*; 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.nextTo..

색종이와 가위 - 20444번

풀이 방법 n 번의 가위질로 만들 수 있는 조각의 개수는 (가로 + 1) * (세로 + 1) 개 이다. 이 문제는 경우의 수가 많아 이분탐색을 사용해서 풀이했다. 가로, 세로 갯수가 같을 때 조각의 개수가 가장 많이 나오게 되어서 이분탐색의 right 값을 N/2로 시작했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new ..

네트워트 연결 - 1922번

풀이 방법 최소 비용 신장 트리를 만드는 문제이다. 그리디 방법을 사용해서 트리를 만들었는데 각 경로를 나타내는 Node 클래스를 만들어서 priorityQueue를 이용했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N = Integer.parseInt(br.readLine()); int M = Integ..

오리 - 12933번

풀이 방법 입력이 어떻게 주어지는지 생각하는 데 시간이 좀 걸렸다. 입력은 무조건 5의 배수의 길이로 주어지지 않고 5의 배수의 길이로 주어졌더라도 오리의 울음소리를 만들 수 있게 딱 나누어 떨어지지 않았다. 녹음한 소리가 올바르지 않은 경우 입력이 5의 배수의 길이로 주어지지 않은 경우 울음 소리를 만들 수 있게 딱 나누어 떨어지지 않은 경우 이 세가지를 생각해서 풀이했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..

운동 - 1956번

풀이 방법 플로이드 와샬 방법을 이용해서 모든 경로를 구해주었다. 자기 자신으로 가는 경로가 있는 경우 사이클이 있는 거라서 그 중 최소 값을 찾아 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int V, E; static int[][] array; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(..

이동하기 - 11048번

DP 를 이용해서 입력 받을 때 바로 그 위치의 최댓값을 구해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N, M; static int[][] array; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Int..

벽 부수고 이동하고 - 2206번

풀이 방법 처음에는 그냥 bfs로 풀이했다가 고생했다. 이 문제는 벽을 부수고 이동할때와 그냥 이동했을 경우 따로 visited를 구분해줘야 한다. 부수고 이동했을때 이전 이동한 경로를 다시 가면 안되지만 부수지 않았으면 부수고 이동했을때 갔던 노드를 가도 된다. 방문체크를 구분해서 해주는 것만 생각해주면 되는 문제이다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { int x, y, distance; boolean check; Node(int x, int y, int distance, boolean check) { this.x = x; this.y = y; this.dist..