본문 바로가기

PS

 (33)
[BOJ] 20500 Ezreal 여눈부터 가네 ㅈㅈ 문제 링크 www.acmicpc.net/problem/20500 풀이 단순한 DP 문제이다. $dp[i][j] =$ $i$자리 수를 15로 나눈 나머지가 $j$인 경우의 수라고 정의하고 풀면 된다. Java 코드 더보기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] dp = new int[1516][15]; dp[1][1] = dp[1][5] = 1; for (int i = 1; i < N; ++i) { for (int j = 0; j < 15; ++j) { dp[i + 1][(..
[BOJ] 1359 복권 문제 링크 www.acmicpc.net/problem/1359 풀이 비트가 M개 켜지는 모든 경우에 대해 $2^M-1$과 겹치는 비트가 K개 이상인 경우의 수를 구해주면 된다. Java 코드 더보기 import java.io.*; import java.util.StringTokenizer; public class Main { public static int bitCnt(int n) { int ret = 0; for (; n > 0; n -= n & -n) ret++; return ret; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..
[BOJ] 20673 Covid-19 문제 링크 www.acmicpc.net/problem/20673 풀이 신규 확진자 $p$는 아무래도 더미 정보인 듯하다. 그냥 $q$를 이용해서 10 이하라면 White, 30 이하라면 Yellow, 나머지는 Red를 출력하면 된다. Java 코드 더보기 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int p = Integer.parseInt(br.readLine()); int q = Integer.parseInt(br.readLine()); i..
[BOJ] 1498 주기문 문제 링크 www.acmicpc.net/problem/1498 풀이 KMP 문제이다. 문자열의 길이가 $a$이고 마지막 인덱스에 해당하는 실패함수의 값이 $b$라고 하자. 이때, $a-b$ 값이 $a$의 약수라면 길이 $a$짜리 문자열은 길이 $a-b$짜리 prefix의 반복임을 알 수 있다. 문제에서 $n$의 값이 1보다 커야 주기문으로 인정하므로, 실패함수의 값이 0보다 커야 한다. 전체 시간복잡도는 $O(|S|)$이다. C++ 코드 더보기 #include #define X first #define Y second #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define ini(x, y) memset(x, y, sizeof(x)) #..
[BOJ] 12760 최후의 승자는 누구? 문제 링크 www.acmicpc.net/problem/12760 풀이 각 플레이어의 카드를 정렬하고 순서대로 큰 값부터 비교하면서 점수를 계산해주면 된다. Java 코드 더보기 List의 배열을 어떤 식으로 만드는지 몰라서 이것저것 시도하다가 동작되는 코드를 찾았다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(n..
[BOJ] 1522 문자열 교환 문제 링크 www.acmicpc.net/problem/1522 풀이 슬라이딩 윈도우 문제이다. a의 개수를 길이로 하는 구간을 잡아서 모든 구간에 대해 탐색하며 해당 구간에 속하는 b의 개수의 최솟값을 찾으면 된다. Python 3 코드 더보기 S = input() a = S.count('a') ans = len(S) for i in range(a - 1, len(S)): ans = min(ans, S[i - a + 1:i + 1].count('b')) for i in range(0, a - 1): ans = min(ans, (S[i - a + 1:] + S[:i + 1]).count('b')) print(ans)
[BOJ] 17091 단어 시계 문제 링크 www.acmicpc.net/problem/17091 풀이 그냥 케이스를 잘 따져서 출력하는 문제. 상당히 귀찮다. Java 코드 더보기 import java.io.*; public class Main { private static String[] hours = new String[]{ "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "one" }; private static String[] minutes = new String[]{ "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "te..
[BOJ] 10823 더하기 2 문제 링크 www.acmicpc.net/problem/10823 풀이 문자를 하나하나 입력받으면서 숫자를 구성하고 누적해주는 방법도 있지만, 언어에 따라 모든 줄을 하나로 이어 붙인 후 콤마(,)로 split해서 정수로 파싱하고 합을 구하는 방법이 더 간단하게 구현될 수도 있다. Java 코드 더보기 import java.io.*; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder dat = new StringBu..

티스토리툴바