백준
백준 JAVA 9613 GCD 합
백준 JAVA 9613 GCD 합
2021.12.31문제 링크: https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net ▶ 해설 n 개의 수가 주어집니다. 각각의 숫자마다의 GCD (최소 공약수)를 구한 후 더한 것을 출력합니다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOExcept..
백준 JAVA 2407번 조합
백준 JAVA 2407번 조합
2021.12.30문제 링크: https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net ▶ 문제 단순히 조합을 구하는 것이지만 5
백준 JAVA 11726번 2xn 타일
백준 JAVA 11726번 2xn 타일
2021.12.29문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ▶ 문제 2xn 직사각형안에 1x2와 2x1 타일을 채운다. ▶ 해설 DP 문제로 판단되어 점화식을 세웠다. 2 = 2 3 = 3 4 = 5 5 = 8 .... 9 = 55 위 처럼 나오므로 점화식은 DP[N]=DP[N-1]+DP[N-2]로 도출 할 수 있었다. import java.io.*; public class Main { public static void main(String[] args) thro..
백준 JAVA 21314번 민겸수
백준 JAVA 21314번 민겸수
2021.12.28문제 링크: https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 문제 풀이 가장 큰 수의 조건 M이 K를 만날 때까지 상태를 유지하는 것이다. ( ex = MMK -> 500, MMMK->5000 ) M이 연속 될 시 1로 상태 변환한다. ( ex = MMM-> 111, MM-> 11 ) 가장 작은 수의 조건 K는 바로 5로 상태 변환한다. ( ex = MMK -> 105, KK -> 55 ) M은 연속 될 시 제곱의 형태로 변환한다. ( ex = MMMK -> 1005, MMMM-> 1000 ) 위의 조건들을 만족시키는 코드..
백준 JAVA 17413번 단어 뒤집기 2
백준 JAVA 17413번 단어 뒤집기 2
2021.12.27문제 링크: https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 해설 ''로 감싸져 있는 문자들은 뒤집지 않고 ' ' 공백으로 나눠져 있는 문자들을 뒤집는다. ''가 등장할 때까지 StringBuilder에 넣어준다. 공백이 나온다면 바로 StringBuilder에 넣어준다. ' ', ''); i=j; } else if(s.charAt(i)==' '){ sb.append(" "); } else{ int j=i;..
백준 JAVA 16916번 부분 문자열
백준 JAVA 16916번 부분 문자열
2021.12.25문제 링크: https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 비교하는 문자열의 길이가 짧다면 반복문을 중첩시켜 구할 수 있겠지만, 두 문자열의 최대 길이가 100만이므로 시간초과가 날 것이다. 따라서 KMP 알고리즘을 사용해야 한다. 해당 알고리즘은 접두사와 접미사를 활용하여 판별한다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int t; sta..