0과 1의 쉼터

문제https://www.acmicpc.net/problem/14335 풀이문자열 S에 대해 순서를 고려한 서로 다른 부분 수열의 수를 구하는 문제다.문자열의 길이가 최대 1,000으로 모든 부분 수열들을 구하고 중복을 제거한다면 시간 초과가 발생한다.순서를 고려하므로 중복되는 문자에 대한 부분 수열을 제거해야 한다.dp[i] : i번까지 문자들로 만들어진 서로 다른 부분 수열의 수중복을 고려하지 않고 부분 수열의 수를 기록하자. long[] dp = new long[N + 1]; dp[0] = 1; for (int i = 1; i 이제 중복되는 요소를 제거해보자.이전에 마지막으로 등장한 S[i - 1]의 위치를 j라고 하자..

문제https://www.acmicpc.net/problem/1354 풀이주어지는 N에 대해 $A_N$을 구하는 문제다.단 N은 최대 $10^{13}$이며, 중복되는 계산을 최소화 해야한다.범위가 넓기 때문에 Map을 사용해서 중간 계산을 기록하면 된다. private static long getA(long i) { if (i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01354.java

문제https://www.acmicpc.net/problem/1052 풀이N개의 병을 2개씩 합쳐서 하나의 병으로 만드는 문제다.만약 K개의 병으로 만들 수 없다면 병을 한 개 더 추가해 다시 합칠 수 있다.2개의 병을 한 개의 병으로 합치기 때문에 N을 최대로 합칠 수 있는 병의 수는 N을 이진수로 했을 때 1의 개수와 동일하다.예제 1번은 다음과 같다.1 1 1 1 1 1 1 1 1 1 1 1 12 2 2 2 2 2 14 4 4 18 4 1$13=1101_{(2)}$으로 필요한 병의 수는 3개지만, K는 2이므로 병을 더 추가해야 한다.$14 = 1110_{(2)}$에 대해 K는 2, 추가된 병은 1개다. 14개의 병을 합쳐 총 3개의 병에 { 8, 4, 2 }담을 수 있다.이를 코드로 구현하면 다음..

문제https://www.acmicpc.net/problem/1025 풀이N*M 의 보드에서 행과 열이 등차수열을 이루는 칸들의 숫자를 이어 붙여 만든 수가, 어떤 정수의 제곱수 중 가장 큰 제곱수를 찾는 문제다.만약 찾지 못했다면 -1을 반환해야 한다. int res = -1; for (int i = 0; i 행과 열에 대한 등차수열이기 때문에 각 위치에 2N * 2M 범위에 대한 등차수열을 찾으면 된다. for (int dx = -N; dx 만약 증가값이 둘 다 0이라면 탐색이 불가능하므로 유의하며, 숫자를 이어 붙인 후 가장 큰 제곱수를 찾아주면 된다. if (dx != 0 || dy != 0) { ..

문제https://www.acmicpc.net/problem/1013 풀이입력으로 주어지는 여러 문자열들이 지문에서 주어진 패턴과 동일한 문자열인지 판별하는 문제다.정규표현식을 사용해 쉽게 풀이할 수 있다. Pattern pattern = Pattern.compile("^(100+1+|01)+$"); while (T-- > 0) { // Solve sb.append(pattern.matcher(br.readLine()).matches() ? "YES\\n" : "NO\\n"); }소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/nor..

문제https://www.acmicpc.net/problem/15685 풀이문제에서 주어진 조건대로 드래곤 커브를 만들고, 네 꼭짓점이 드래곤 커브의 일부분인 1x1 크기의 정사각형의 수를 세는 문제다.우선, 드래곤 커브의 규칙부터 알아보자.시작점에서 시작방향으로 1칸 이동 후 끝점을 기준으로 지금까지 그린 드래곤 커브를 시계 방향으로 90도 회전해야 한다.이때, 드래곤 커브의 모든 변은 위치와 방향에 관계없이 결국 시계 방향으로 90도 회전을 한다.0: x좌표가 증가하는 방향 (→)1: y좌표가 감소하는 방향 (↑)2: x좌표가 감소하는 방향 (←)3: y좌표가 증가하는 방향 (↓)방향 변화에 대해 다음과 같은 규칙이 성립한다.0 → 11 → 22 → 33 → 0각 부분 드래곤 커브들의 방향 변화 규칙..

문제https://www.acmicpc.net/problem/3980 풀이11명의 선수들이 각 포지션에서의 적합한 능력치를 바탕으로 모든 포지션에 배치했을 떄, 선수들의 최대 능력치 합을 구하는 문제다.완전 탐색을 통해 충분히 구할 수 있으나, 여러 TC가 존재하기 때문에 최적화를 진행해야 한다.한 선수는 11개 중 최대 5개의 포지션에 대한 능력치를 가질 수 있다.따라서 능력치가 0보다 큰 경우에 대해서만 탐색하면 된다. private static int bt(int sum, int i) { if (i == 11) { return sum; } int res = 0; for (int j = 0; j 0) { ..

문제https://www.acmicpc.net/problem/18405 풀이N * N크기의 보드에서 번호가 낮은 바이러스부터 상하좌우로 증식한다.이 때, S초 후 ( X, Y )에 위치한 바이러스를 출력하는 문제다.우선 ( X, Y )에 시작부터 바이러스가 있을 수 있다. 확인 후 탐색을 진행하자. private static int bfs() { if (A[X - 1][Y - 1] != 0) return;번호가 낮은 바이러스 먼저 증식해야 하기 때문에 바이러스를 찾아, 바이러스 번호에 대해 오름차순으로 정렬 후 큐에 담아주자. List list = new ArrayList(); for (int i = 0; i 0) { ..

문제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..