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

징검다리 건너기 - 21317번

풀이 방법 다이나믹 프로그래밍을 사용해서 풀이했다. 중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다. 그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다. 나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

스티커 - 9465번

풀이 방법 DP의 Bottom-Up 방식을 이용해서 풀이했다. 맨앞의 스티커 두개를 먼저 넣어주고 다음 스티커부터 대각선방향으로 더한 값과 서로 변을 공유하는 스티커 중 더 큰값을 찾아주었다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; 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 StringTo..

좋은 수열 - 2661번

풀이 방법 DFS에서 조건을 걸어 백트래킹으로 풀이했다. 먼저 좋은 수열인지 아닌지 판단하는 check 함수를 작성해주었다. 가장 작은 수를 나타내는 수열을 찾기 위해 DFS에서 1,2,3 순서대로 확인해 주었다. 길이가 N과 같게 되면 find 를 true 로 해줘서 return 하는 것으로 구현했다. 내 코드 package com.company; import java.io.*; public class Main { static int N; static Boolean find = false; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

말이 되고픈 원숭이 - 1600번

풀이 방법 BFS를 이용해서 최단경로를 구하는 방법을 이용했다. 이동할 수 있는 동작마다 if문을 이용해서 우선순위 큐에 넣어주었다. 여기서 방문을 체크하는 visited를 조심해야 했다. 그냥 테이블과 동일하게 visited를 구현하게 되면 말처럼 움직이는 동작과 그냥 인접한 칸으로 움직이는 동작을 구분하지 않게 된다. 그래서 말처럼 움직이는 동작을 한 횟수별로 따로 visited 테이블을 만들어주어야 한다. 나머지는 기본 BFS 동일하게 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int x; private int y; private int..

뒤집기 II - 1455번

풀이 방법 a, b칸을 뒤집으면 하위 모든 칸들이 뒤집히기 때문에 맨 위에서부터 확인해서 뒤집어 주었다. 세로와 가로 둘다 줄여 나가는것이 아닌 한쪽만 기준으로 잡고 줄여나가도 된다. 내 코드 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.pars..

알바생 강호 - 1758번

풀이 방법 최대로 팁을 받기 위해서는 내림차순으로 정렬해서 더해주면 된다. tip의 타입을 int가 아닌 long으로 선언해주는 것만 주의하면 된다. 내 코드 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)); int N = Integer.parseInt(br.readLine()); Integer array[] = new Integer[N]; Long tip = 0L; for (i..

숨바꼭질 3 -13529번

풀이 방법 2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다. Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다. 풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다. BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다. 가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node { private int N; priva..

DFS와 BFS - 1260번

풀이 방법 전형적인 bfs, dfs 문제로 풀어보면 둘의 차이점을 잘 알 수 있다. 방문할 수 있는 정저미 여러개인 경우 정점 번호가 작은것을 먼저 방문한다는 조건으로 정렬한번만 해주면 되는 문제 였다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static ArrayList graph = new ArrayList(); static Boolean[] visited; static int N, M, V; static void dfs(int V) { visited[V] = true; System.out.print(V + " "); for (int i = 0; i < graph.get(V).size(); ..

저울 - 10159번

풀이 방법 모든 물건에서 비교 결과를 알 수 없는 물건의 개수를 출력해야 되기 때문에 플로이드-와셜을 사용했다. 일단 비교 결과를 저장할 테이블을 만들고 100으로 채워넣었다. (그냥 비교 할 수 없는 경우를 100 으로 사용했음) 자기 자신과 비교는 0으로 바꿔주었다. 내가 비교하는 수보다 크면 1, 작으면 -1 로 두었다. 플로이드-와셜을 사용해서 두 수를 비교할 때 중간에 낄수 있는 수가 있으면 넣어 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

백도어 - 17396번

풀이 방법 다익스트라로 최단 경로를 구하는 문제이다. 최단 경로를 구하는 과정에서 지나간 지점인지 확인할 때 시야가 보이는 지점인지 확인해서 경로를 지나가지 않도록 설정하고 시야가 보이더라도 넥서스라면 경로가 지나가도록해서 최단경로를 구하도록 구현했다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int index; private Long distance; public Node(int index, Long distance) { this.index = index; this.distance = distance; } public int getIndex() { ret..