https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N, M, tmpN = 0, cnt = 0; static String S; public static void ..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] tree; static int N, M, mid; static long tmpSum, ans = 0..
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStre..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int s, e, answer = 0, lastEnd = 0; static StringTokenizer st; static List schedule; public static void main(String[] args) throws IOException { Buffe..
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net import java.util.*; public class Main { static int N, M, n1, n2; static int[][] kbNum; static ArrayList[] edges; static boolean[] visited; public static void main(String[] args) { Scanner sc = new..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 💡유형 : 브루트포스 가능한 수들을 조합해 1차적으로 수를 만든 뒤, 거기서 + / - 해서 N에 도달해야 함 가능한 번호로 숫자를 조합하는 과정에서 완전 탐색 진행함 주의해야 할 점 가능한 숫자 조합에서 N으로 도달할 때 +/- 버튼 누르는 횟수에 숫자 만드는데 누른 버튼 횟수를 더해야 함 100에서 바로 +- 누르는게 제일 빠를 수 있으므로 cnt = |N - 100|로 세팅..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP문제라고 해서 규칙성 찾는 것에 너무 매몰되지 말 것. 전반적인 흐름을 보자 길이가 N-1인 계단수의 개수가 An-1이라면, An = 2*An-1 - (N-1에서 1, 8의 개수) 9 - (9*2-1 = 17) - (17 * 2 - 2 = 32) ... 그 전 자릿수가 k였다면, 다음 자릿수로는 k+1, k-1이 가능하다. 전 자릿수가 1, 8인 경우 0, 9 가 발생 된다. 1, 8의 개수는 결국 0, 2, 7, 9의 개수와 동일함 -> 얘만 볼게 아니라 전체적으로 따지는게 편함 dp[N-1][K] : 길..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N; static int[] stairs; static int[][] dp; public static void main(String[] args) throws IOException { Buf..
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[N + 1]; dp[0] = 1; dp[1] = 1; if(N >= 2) { for (int i = 2; i 2)
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main_1038 { static List numbers = new ArrayList(); public static void main(String[] args) { Sca..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 시간 복잡도를 고려해서 생각할 것... 재귀로 풀어서는 택도 없음 -> 저번 문제처럼 dp를 사용하자 더보기 틀린 코드 - 재귀 활용 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main_2294 { static int n, k, tmp, min; s..
