철학하는 개발자

있는 것은 있고, 없는 것은 없다.

Normal 58

[백준 11049] 행렬 곱셈 순서 [Java]

문제11049번: 행렬 곱셈 순서 11049번: 행렬 곱셈 순서 boj.ma 풀이문제 요약행렬 N개의 곱셈 순서를 적절히 정해, 곱셈 연산 수의 최소값을 구해야 한다.아이디어행렬 곱셈은 결합 순서에 따라 계산 비용이 달라진다.따라서, 각 구간 [L, R]을 적절히 나누는 위치 t를 찾아 최소 비용을 계산해야 한다.점화식은 다음과 같다.dp[L][R]: L ~ R 구간의 최소 곱셈 비용dp[L][R] = dp[L][t] + dp[t + 1][R] + (matrix[L][0] * matrix[t][1] * matrix[R][1])행렬이 1개 일 때행렬이 1개 일 때, 즉 L == R일 때는 연산을 하지 않으므로, dp[L][L] = 0이 된다. // Solve int[][] dp =..

[백준 02225] 합분해 [Java]

문제2225번: 합분해 2225번: 합분해 boj.ma 풀이정수 K개의 합이 N이 되도록 만드는 경우의 수를 세는 문제다.덧셈의 순서가 바뀐 경우는 다른 경우이지만, 동일한 수에 대한 연산은 하나의 경우로 볼 수 있다.ex) 1+2, 1+2는 다른 경우, 1+1, 1+1은 피연산자의 순서는 다르지만, 덧셈의 순서(?)는 다르다.dp[N][K] : 정수 K로 N을 만드는 경우의 수초기값부터 설정하자.dp[0][K]인 경우 0만 가능하다. for (int k = 1; k dp[N][1]은 N자신만 가능하다. for (int i = 1; i dp[N][K]는 dp[N - 1][K]의 맨 뒤 요소를 1늘리는 경우와dp[N][K-1]에 0을 추가해주는 경우로 볼 수 있다. f..

[백준 14335] 서로 다른 부분 수열의 개수 [Java]

문제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라고 하자..

[백준 01052] 물병 [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 }담을 수 있다.이를 코드로 구현하면 다음..

[백준 01025] 제곱수 찾기 [Java]

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

[백준 01013] Contact [Java]

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

[백준 15685] 드래곤 커브 [Java]

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

[백준 03980] 선발 명단 [Java]

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

[백준 18405] 경쟁적 전염 [Java]

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