본문 바로가기

전체 글

 (44)
[Java] BOJ14500_테트로미노 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 각 칸에 가능한 테트로미노의 모양을 다 놓아보고 최댓값을 찾는 문제이다. i 행 j 열이 노란색칸일 때 가능한 테트로미노 모양은 위와 같이 19가지가 나오며 이 모양들 중 배열의 범위를 벗어나지 않는 모양들을 놓아보고 각 칸의 합을 구해 최댓값을 구한다. import java.io.*; import java.util.StringTokenizer; public class Main { static int N, M;..
[Java] BOJ1421_나무꾼 이다솜 www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 1부터 가장 긴 나무의 길이까지 모든 나무를 잘라봐야 한다. 이때 자르는 길이보다 짧은 나무는 자를 수 없다. 자를 수 있는 모든 나무에 대해 K * L * W - (C * 자른 횟수)를 구해서 합해준 후 최댓값 비교를 한다. 여기서 주의할 점은 K * L * W - (C * 자른 횟수) 값이 음수가 나와서 합해줄 때 손해인 경우는 합하지 않아야한다. 위 처리를 안 해줄 경우 자르는 비용이 터무니없이 클..
[Java] BOJ13458_시험 감독 www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 단순 구현문제이다. "각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다." 이 부분에서 총 감독관이 반드시 1명 있어야한다는 뜻이 없지만 예제의 출력을 봤을 때 반드시 1명 있어야하는 것을 알 수 있었다. 따라서 시험장 인원이 총감독관 한명으로 다 감독 가능하면 결과를 1 증가시켜줬고 그 경우가 아닐 때는 총감독관이 감..
[Java] BOJ13410_거꾸로 구구단 www.acmicpc.net/problem/13410 13410번: 거꾸로 구구단 일반적인 구구단에서 가장 큰 수는 마지막 항의 값이 제일 크다. 거꾸로 구구단에서는, 각 항에 구구단의 계산 결과로 나온 값을 뒤집어 저장을 한다. 이렇게 하면 가장 큰 값이 항상 마지막이 www.acmicpc.net 단순 브루트 포스 문제이다. 기존 구구단 값을 구하고 문자열로 바꿔주어 뒤집어주고 다시 int로 바꿔 비교해서 최댓값을 찾아냈다. import java.io.*; import java.util.StringTokenizer; public class Bj13410 { public static void main(String[] args) throws IOException { BufferedReader br = ne..
[Java] BOJ13164_행복 유치원 www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 정렬이 되어 있는 데이터에서 최소를 뽑으려 하는 점에서 그리디를 유추했다. 구하고자 하는 값이 키 차이의 최소이기 때문에 연속된 두 학생의 키 차이를 구해 N-1 크기의 배열을 만들었다. 이 배열에서 작은 키차이를 골라야 하기 때문에 정렬을 하였다. 이제 이 키 차이 중 몇개를 골라내야 하는지 알아야 한다. 예제의 경우 이런 식으로 나누어지고 [3, 5], [6, 10]의 키 차이가 제외..
[Java] BOJ12015_가장 긴 증가하는 부분 수열 2 www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 최장 증가 부분 수열 문제이다. 하지만 N의 범위가 크기 때문에 단순 이중 반복문으로는 해결이 되지 않는다. 이 경우에는 이분 탐색을 사용해야 한다. dp 배열에는 최장 증가 부분 수열을 이루는 요소가 담긴다. 하지만 주의할 점은 이 요소들이 항상 최장 부분 수열이라는 것을 보장하지는 않는다. 그저 개수만 맞을 뿐이다. 정확한 요소를 골라내기 위해서는 다른 방법을 사용해야 한다. 하지만 이 문제는 개수만 구하면..
[Java] BOJ1197_최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 제목 그대로 최소 스패닝 트리(MST)를 구하는 문제이다. MST 알고리즘에는 대표적으로 Prim과 Kruskal 알고리즘이 있다. Prim 알고리즘은 V^2의 시간 복잡도, Kruskal은 ElogE의 시간 복잡도를 가진다. 하지만 Prim알고리즘을 우선순위 큐를 이용하여 구현할 시 ElogV의 시간 복잡도로 이 문제에서 가장 빠르게 해결할 수 있다. 가중치..
[Java] BOJ15961_회전초밥 www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 꽤나 시간이 빡빡한 문제이다. 초밥을 선택할 때 중복되는 부분이 많으므로, 예제 1의 경우 위와 같이 탐색을 할 것이다. 이런 방법을 슬라이딩 윈도우라고 한다. 회전초밥 테이블이 원형이기 때문에 '25' 같은 경우 앞에 있는 [7, 9, 7]과 연결되어 탐색해야 한다. 따라서 탐색을 더 쉽게 하기 위해 앞에서부터 K-1개의 값들을 배열에 더 추가해줬다. 최종적으로 배..

티스토리툴바