백준

숨바꼭질 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 = ..

1로 만들기 - 1463번

풀이 방법 생각 DP 문제로 점화식을 생각해야 했다. 일단 0과 1은 0번으로 고정이라서 값을 넣어주었다. Bottom-up 방식으로 2부터 n까지 계산해 주었다. 이전 수에서 1을 더하는 경우를 생각해서 이전 수의 횟수에서 1을 더해주는 경우 2로 나누어 떨이지기 때문에 2로 나눈 수의 횟수에 1을 더하는 경우 3으로 나누어 떨어지기 때문에 3으로 나눈 수의 횟수에 1을 더하는 경우 이 세가지를 비교해서 최솟값을 만들어 주었다. 내 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Mai..

트리의 부모 찾기 - 11725번

트리의 부모 찾기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 27396 11727 8664 42.697% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 예제 입력 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 예제 ..

나는야 포켓몬 마스터 이다솜 - 1620번

나는야 포켓몬 마스터 이다솜 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 26947 8852 6287 32.421% 입력 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 ..

요세푸스 문제 - 1158번

요세푸스 문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 50463 24503 17494 48.004% 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, )-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ ..