문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 코드 import java.io.*; import java.util.*; class Main { public static void main(String args[]) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = n..
문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 Arrays.sort() 만 쓰다보니 Arrays.sort() 에만 익숙해졌다.😥 문제를 보면 N이 10,000,000 까지 간다. 메모리 초과가 일어날 수도 있고 간당간당하게 통과될수도 있다. 따라서 Counting Sort 를 이용한다. 10000 이하의 수가 입력이 된다. 따라서 배열의 크기를 10001 로 선언한다. 그리고 입력되는 수가 index가 되고 입력되는 숫자가 등장하는 만큼 배열의 값을 ..
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 코드 import java.io.*; import java.util.*; class Main{ static int k, w, h; static int board[][]; static int visited[][][]; public static void main(String[] args) throws Exception { BufferedReader br = new Buffered..
문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 import java.io.*; import java.util.*; class Main{ static int k, n; static int arr[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRead..
문제 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 배열안의 세 수를 더하고 그 값이 배열안에 있는지 확인하는것은 4중 for문을 이용하면 구할 수 있다. 그러나, 문제에서 N이 1000이하이기 때문에 최악을 고려하면 O(n^2) 이나 O(n^2logn)의 시간 복잡도가 나와야 문제가 풀린다. 이 문제는 이진탐색 카테고리에 있는 문제이기 때문에 이진탐색을 이용해야 한다. a[i] + a[j..
문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 양수끼리 곱해야 값이 커지고 음수끼리 곱해야 값이 커진다. 따라서 양수끼리 리스트에 넣고 음수끼리 리스트에 넣는다. 양수끼리 곱할때는 큰것부터 곱해야 하므로 내림차순으로 정렬하고 음수끼리 곱할때는 작은것 부터 곱해야 커지기 때문에 오름차순으로 정렬한다. 양수끼리 곱할때 주의해야 할 것은 1이다. 즉, 1과 양수를 곱하면 값이 그대로이기 때문에 이때는 곱하는 것보다는 더하는게 더 낫다...
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 import java.io.*; class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long dp..
문제 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.ArrayList; import java.util.LinkedList; ..
문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 코드 import java.io.*; import java.util.*; public class Main { static int n; static int board[][]; static int dx [] = {-1, 0, 1, 0}; static int dy [] = {0, 1, 0, -1}; static int min = Integer.MAX_VALUE; public static void mai..
문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net knapsack 알고리즘을 사용하는 문제였다. https://st-lab.tistory.com/141 를 보고 알고리즘을 이해할 수 있었다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) thro..
