문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 이차원 배열을 이용하여 세가지 경우의 수를 나타낸다. dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우 dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우 dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우 코드는 다음과 같다 dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) => 넣지 않을 것이므로 그 전은 상관 없다 dp[i][1] = (dp[i-1][0] + dp[i-1][2]) => 왼쪽에 넣기 때문에 이전방은 오른쪽이거나..
문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 빗물이 고이려면 다음과 같아야 한다. 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다. 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다. 첫, 마지막 블록에는 빗물이 고일 수 없다. 각 인덱스를 기준으로 오른쪽과 왼쪽의 높은 블록을 구하고 차이값을 구한다. 코드 import java.util.*; import java.io.*; public class Ma..
문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Strin..
문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 풀이 백트레킹을 이용하여 푸는 문제 부등호에 따라 크기를 비교해야 되며, 중복된 숫자가 올수 없다. 따라서, 숫자가 중복되었는지 판단하는 배열, 부등호를 저장하는 배열, 결과값을 저장하는 리스트가 있어야 한다. 중복된 숫자가 들어가면 안되기때문에 visited 배열을 이용하여 이미 사용한 숫자면 continue, 그렇지 않다면 다음 index로 넘어간다. 숫자가 부등호 조건에 맞는지 탐색한..
문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 단순히 정렬하고 가운데 값을 찾아주면 N*N*logN의 시간복잡도가 발생한다. 두 가지 공간을 두고 하나는 작은 값을 넣는 공간, 하나는 큰 값을 넣는 공간으로 만들어준다. 작은 값을 넣는 공간은 maxHeap으로 큰 값을 넣는 공간은 minHeap으로 만들어준다. 두 개의 PriorityQueue의 크기가 같은 경우 maxHeap에 입력된 값을 추가한다. 입력한 값이 ..
문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 우선순위 큐를 이용한 문제 가장 작은 것들 두개를 뽑아서 더해주고 그 값을 다시 우선순위 큐에 넣는 과정을 반복한다. 생각해볼것은 두가지이다. 1. n=1일때 n이 1일때에는 합칠수가 없다. 따라서 결과값은 0이된다. 2. 변수 타입 1000이 10000번 입력이 된다면 int 범위보다 더 크게 된다. 따라서 long으로 변수타입을 선언해야 한다. 코드 import jav..
문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static ArrayList arr[]; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(..
문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static int n; static int board[][]; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStr..
문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static int n; static int board[][]; static int answer[] = new int [3]; public static void main(String args[]) throws IOException { BufferedReader br = ne..
문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.pars..
