0과 1의 쉼터

문제https://www.acmicpc.net/problem/19621 풀이N개의 회의실 정보와, 회의 참여 인원이 시간 순서대로 주어졌을 때회의를 진행할 수 있는 최대 인원을 구하는 문제다.문제에서는 K번째 회의는 K - 1, K + 1번째 회의와 시간이 겹치지만, 다른 회의와는 시간이 겹치지 않는다고 명시되어있다.dp로 쉽게 풀이할 수 있다.dp[i] : i 번째 회의까지 참석 가능한 최대 인원 수dp[i - 2]에 현재 회의를 진행하는 것과, dp[i - 1]을 그대로 진행하는 것 중 선택하면 된다.따라서 점화식은 다음과 같다.dp[i] = max(dp[i - 1], dp[i - 2] + 1) dp[1] = A[1]; for (int i = 2; i 소스코드https://g..

문제https://www.acmicpc.net/problem/30389 풀이주어지는 N개의 문자열에 대해 모든 부분 접미사 집합을 구하고, 다음 문자열의 접미사 집합과 XOR연산을 하는 문제다.우선 현재 문자열의 접미사를 구해주는 메서드를 만들자.입력받은 문자열을 역순으로 한 칸씩 늘려가며 문자열을 결합해서 저장하면 된다. private static List getSuffixes(String s) { StringBuilder sb = new StringBuilder(); List suffixes = new ArrayList(); for (int i = s.length() -1; i >= 0; --i) { sb.append(s.charAt(i)..

문제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/17521 풀이가격이 낮을 때 사고 높을 때 팔아서 마지막에 얻는 최종 현금의 최댓값을 계산하는 문제다.사고 파는 과정에서 최종 현금은 매우 커질 수 있다. long으로 계산해야 한다.항상 구매 또는 판매 가능한 최대 수량의 코인을 거래하는 것이 좋다.현금이 항상 나누어 떨어지지 않으니 나머지가 있음에 유의하자. // Solve long coin = 0; for (int i = 1; i A[i - 1]) { coin = W / A[i - 1]; W %= A[i - 1]; } else if (coin > 0 && A[i] 마지막에 코인..

문제https://www.acmicpc.net/problem/14007 풀이주어진 시퀀스에 대해 문제에서 주어진 이상한 구간의 수를 구하는 문제다.이상한 구간은 다음과 같다.자기 자신은 이상한 구간이 된다.이전 요소의 차와 현재 요소의 차가 부호가 다르면 이상한 구간이 된다. // Solve int cnt = N; for (int i = 0; i 요소의 차가 0이거나, 이전 요소의 차와 현재 요소의 차가 동일할 때는 이상한 구간이 아니게 된다.위 조건문을 통해 이상한 구간이 맞다면 탐색을 중단하고, 다음 구간에 대한 탐색을 진행하자. if (diff == 0 || prevDiff != 0 && diff * prevDiff > 0) { ..

문제https://www.acmicpc.net/problem/20410 풀이입력으로 주어지는 m, Seed, $X_1$, $X_2$에 대해X1 = (a × Seed + c) % mX2 = (a × X1 + c) % m을 만족하는 a, c를 출력하면 된다.a, c의 범위는 0 ~ m - 1 이며 m은 100이하의 소수이므로 완전 탐색으로 풀이가 가능하다. for (int a = 0; a 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/20410.java

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