문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 푸는 문제다. 문제에서 제곱수의 배수로 나누어 떨어지지 않을 경우 제곱 ㄴㄴ 수라고 하였다. 소수를 구할 때 에라토스테네스의 체에서는 소수의 배수들을 모두 제거했다. 마찬가지로 이 문제에서는 제곱수의 배수들을 모두 제거하면 된다. 문제는 두 가지다. min이 최대 1,000,000,000,000 이 될 수 있다는 점 타임 컷팅 1번은 쉽다...
문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 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 task..
문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 대충 보고 풀었다가 틀렸다. 문제를 제대로 보고 풀도록 하자 문제자체는 쉽다. 맨 앞 문서의 우선순위와 나머지 문서의 우선순위를 비교해서 맨 앞 문서 우선순위가 가장 크다면 출력하고(빼고) 나머지가 더 크다면 맨 뒤에 넣는다. 문서를 출력했을때 원래 M번째 문서를 출력했다면 몇번째만에 출력했는지 표시한다. 여기서 내가 행한 문제점은 문제의 설명만 보고 대강 우선순위 높은 데이터가 나간다고 ..
문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 BFS 탐색 알고리즘을 사용하여 문제를 풀었다. 우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다. 코드 import java.util.*; import java.io.*; public class Mai..
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 단순한 DP문제인줄 알았는데 한단계 더 생각해야 했던 DP문제다 dp[i] => i번째 잔까지 마실 수 있는 와인 최대 양 문제에서 연속으로 놓여 있는 3잔을 모두 마실 수는 없다고 한다. 따라서 경우의 수는 다음과 같이 나온다. 3번째 잔을 선택했다고 하자 1. 와인순서 1 2 3 4 5 6 7 선택 여부 O O X 2. 와인순서 1 2 3 4 5 6 7 선택 여부 O O X 3. 와인..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹 문제 백트래킹에서 가장 중요한 것은 가지치기이다. 이 문제에서는 가지치기를 start를 매개변수로 사용해서 수행한다. 즉, for문을 돌때 백트래킹을 하게 되면 이전 요소들은 이미 수행되었기 때문에 다음 요소에 대해서 백트래킹을 하면 된다. 따라서, start를 매개변수로 하여 가지치기를 수행한다. 선정한 치킨집이 M개가 되었다면 visited 배열에는 M..
문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 에라토스테네스의 체를 이용하여 풀면 되는 정석 문제다 코드 import java.io.*; import java.util.*; public class Main { public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..
문제 https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,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..
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 DP 문제다. 2x3 경우를 생각해보자 n은 열의 개수를 나타내고 dp[n] 은 2xn일때 만들 수 있는 경우의 수를 나타낸다. 노란색 : 3번째 칸을 2x1로 놓았을 경우 dp[2]이 그대로 dp[3]이 된다. 파란색 : 3번째 칸을 2x1로 놓지 않았을 경우 2x2 혹은 1x2를 사용할 수 있다. 이는 dp[1]과 2가 곱해져야 한다. 따라서 dp식은 다음과 같다. dp[3] = dp[i-1] + dp[i-2] ..
문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 모든 가로수가 같은 간격이 되도록 심어야 한다. 이미 몇몇 가로수들은 심어져 있다. 그러면 가로수 간격이 모두 같으려면 어떻게 해야될까?이는 초등학교 수학문제에서 답을 찾을 수 있는데 바로 최대공약수이다.최대공약수를 이용하여 가로수의 간격을 구하고 이 간격에 따라서 가로수를 심어주면 된다.최대공약수를 구할때는 유클리드 호제법을 이용하였다. 유클리드 호제법은 x, y 의 최대공약수..
