0과 1의 쉼터

문제https://www.acmicpc.net/problem/1405 풀이로봇이 확률에 따라 상하좌우로 움직인다고 한다.이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.if __name__ == '__main__': visited = [[False] * 29 for _ in range(29)] # Input N, *D = map(int, input().split()) D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1)..

문제https://www.acmicpc.net/problem/22943 풀이0 ~ 9 중에서 서로 다른 K개를 골라 만들 수 있는 수 중 다음을 만족하는 수를 구해야 한다.서로 다른 두 개의 소수의 합으로 나타낼 수 있어야 하고,M으로 나누어 떨어지지 않을 때 까지 나눈 수가 두 개의 소수의 곱인 경우이어야 한다.구현할 부분이 많지만, 하나씩 해결해보자.0 ~ 9로 K자리 수 만들기우선 0 ~ 9 중 K개를 골라 수를 만들어야 한다.숫자를 한 번씩 만 사용해야 하고, 첫 번째는 0이 올 수 없다. private static void solve(int digit, int num) { if (digit == 0) { // base case } fo..

문제https://www.acmicpc.net/problem/2436 풀이두 수 A, B의 GCD, LCM이 주어질 때, 두 수의 합이 최소가 되는 수를 구하는 문제다.이때 두 수의 범위 2 ~ 1억에 대해 GCD, LCM을 전부 구해 비교하는 방법은 시간 초과가 발생한다.탐색 범위를 좁혀보자.$G = GCD(A, B), L = LCM(A, B)$일 때, $AB = GL$, $A = Gx$, $B = Gy$이므로 $AB = G^2xy = GL, xy = \frac{L}{G} = K$가 성립한다.K의 모든 약수 쌍 중 $GCD(A, B) = G*GCD(x, y)$를 만족해야 하므로, $GCD(x, y) = 1$인 약수만 해당된다. K = LCM // GCD x, y = 0, 0 for d ..

문제https://www.acmicpc.net/problem/3055 풀이S에 위치한 고슴도치가 비버의 굴 D로 이동하는데 필요한 최소 시간을 구하는 문제다.동시에, 물 또한 인접한 영역으로 퍼져나간다.물이 찰 예정인 영역은 고슴도치가 갈 수 없다. → 고슴도치보다 물 먼저 퍼져야 한다.물은 비버의 굴로 퍼질 수 없다.우선, 상수들을 정의해주자. final static char EMPTY = '.', WATER = '*', START = 'S', END = 'D'; static int[][] D = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; static int R, C; static char[][] board; ..

문제https://www.acmicpc.net/problem/16400 풀이N 이하의 소수들을 사용하여 N을 표현할 수 있는 방법의 수를 계산하는 문제다.우선 N이하의 소수들을 구해주자. private static boolean isPrime(int num) { final int sqrtN = (int) Math.sqrt(num) + 1; for (int i = 2; i List primeList = new ArrayList(); for (int i = 2; i dp[i] : 소수들의 합으로 숫자 i를 만드는 경우의 수dp[i]의 i는 소수의 합이기 때문에 dp[i]는 dp[i - prime]에 prime을 더하는 경우의 수를 누적하면 된다.즉 i..

문제https://www.acmicpc.net/problem/3151풀이N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 발생한다.N^2 탐색으로 두 수를 고른 후, 이분 탐색으로 나머지 수를 찾으면 된다.두 수를 0부터 차례대로 완전 탐색을 하기 때문에 이분 탐색의 범위는 ( b + 1 ) ~ ( N - 1 ) 가 된다.이 때, 두 수 a, b에 대해 c가 1개가 아닐 수 있다.upper - lower로 동일한 c의 개수를 세주자.소스코드보기ttps://www.acmicpc.net/problem/3151 풀이N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 ..

문제https://www.acmicpc.net/problem/1477 풀이구간 1 ~ (L - 1)에 N개의 휴게소가 위치 A[i]에 존재하고, M개의 휴게소를 추가로 지었을 때, 휴게소가 없는 구간의 길이의 최댓값이 최소가 되도록 해야 한다.문제의 설명에서 알 수 있듯.M개의 휴게소를 전부 설치 가능한 경우에 대해휴게소가 없는 구간의 길이의 최댓값이 최소가 되어야 한다.휴게소가 없는 구간의 길이를 탐색 범위로 잡고, 이분 탐색을 하면 된다.배열 A의 앞 뒤에 경계 값을 붙여주어 계산을 쉽게 해보자.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException..

문제https://www.acmicpc.net/problem/14921 풀이N개의 수 중 두 수의 합을 0에 최대한 가깝게 만드는 문제다.우선, A를 오름차순으로 정렬해 문제를 단순화하자.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Input final int N = Integer.parseInt(br.readLine()); i..

문제https://www.acmicpc.net/problem/2565풀이유명한 LIS 문제다.우선, 전깃줄의 위치 정보를 A 또는 B를 기준으로 정렬하자.A를 기준으로 정렬해보겠다.A에서 B로 가는 전깃줄이 교차하지 않도록 최소한의 전깃줄만 제거해야 한다.교차하지 않는 전깃줄들이 최대가 되기 위해서는 A에서 B로 향하는 전깃줄들이 최대한 촘촘히 위치가 증가해야 한다.즉 B의 LIS가 교차하지 않는 전깃줄의 수와 동일하다.문제에서 요구하는 정답은 제거해야 하는 전깃줄의 수 이므로 N에서 B의 LIS를 뺀 값을 출력하자.소스코드보기

문제https://www.acmicpc.net/problem/11000풀이강의실을 최소로 사용해서 모든 강의를 끝내야 한다.강의가 끝나는 대로 다음 강의를 바로 진행할 수 있지만, 강의가 끝나지 않았는데 시작하는 강의가 있다면 강의실이 필요하다.priority queue를 사용해 쉽게 해결할 수 있다.우선, 시작 시간을 기준으로 정렬해주자.다음으로 강의 종료시간을 우선순위 큐에 넣어준다.만약 다음 강의의 시작시간이 가장 빨리 끝나는 강의의 종료시간 이후라면, 가장 빨리 끝나는 강의를 우선순위 큐에서 제거해주면 된다.그렇지 않는 경우라면 계속 우선순위 큐에 넣어주고 마지막에 전체 크기를 출력해주자.소스코드보기