[유클리드 호제법] / [백준(baekjoon) 1934] 최소공배수(LCM) 문제 백준 1934 최소공배수(LCM) 를 구하시오. 원리 최소공배수(LCM) A,B의 최소공배수 = A * (B/최대공약수) 최대공약수 : 유클리드 호제법 사용 유클리드 호제법, GCM, LCD 설명 포스트 참고! 구현 java 1.import java.util.*; 2. 3.public class Main { 4. public static void main(String[] args) { 5. Scanner sc = new Scanner(System.in); 6. int n = sc.nextInt(); 7. for (int i = 0; i < n; i++) { 8. int a = sc.nextInt(); 9. int b = ..

[백준(baekjoon) 1780] 대회 or 인턴 문제 백준 1780 N x N 크기의 행렬은 -1, 0, 1의 값을 가진다. 다음과 같은 규칙으로 종이를 자른 후, -1, 0, 1로만 채워진 종이의 개수를 차례대로 출력하시오. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 해결 알고리즘 전형적인 분할 방식 문제이다. 방법 큰 종이를 9개의 작은 종이로 나누는 과정을 반복한다. 시작점, n을 매개변수로 받아 구하고자 하는 종이의 크기 및 값들에 접근할 수 있다. 3 * 3 for문을 돌린다. 작은 종이의 크기는 n / 3이 될 것이다. 종이의 크기 n == 1까..

문제 백준 2011 5000자리 이하의 입력 값(숫자)이 주어질 때, 아래와 같은 규칙으로 암호화 할 때, 가능한 문자의 경우의 수는 A : 1, B : 2, … , Z : 26 예시 : 25114를 영어로 바꾸면 ”BEAAD” = {2, 5, 1, 1, 4} “YAAD” = {25, 1, 1, 4} “YAN” = {25, 1, 14} “YKD” = {25, 11, 4} “BEKD” = {2, 5, 11, 4} “BEAN” = {2, 5, 1, 14} 해결 정답률이 낮아서 어려울지 알았지만, DP를 사용하면 생각보다 간단하게 풀린다. 그런데 엄청 틀렸다. 예외처리를 안했기 때문…. 내 생각에 이 문제는 DP가 아니라 예외처리 문제이다…. 예외처리 문제만 읽고 처음엔 0 input이 안 들어오는줄 알았지만..

문제 백준 2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하시오 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 한 개의 수를 여러 번 쓸 수도 있다. 해결 결론부터 말하자면 다음과 같은 규칙이다. n = 1 : dp[n][k] = k; k = 1 : dp[n][k] = 1; else : dp[n][k] = dp[n - 1][k] + dp[n][k - 1]; 어떻게? n = 2, k = 3일 경우를 보자. dp[n - 1][k]의 각 케이스 마지막 숫자에 + 1을 해주면 k개의 숫자를 활용해 n을 만들 수 있다. dp[n][k - 1]의 각 케이스에 + 0을 해주면 k개의 숫자를 활용해 n을 만들 수 있다. 알고리즘 DP로 풀었고, bot..

[백준(baekjoon) 2133] 타일 채우기 문제 백준 2133 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. N(1 ≤ N ≤ 30) 해결 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 방법 자세한 설명을 뒤로 하고, 간단하게 핵심만 우선 정리하겠다. N이 홀수일 때 경우의 수는 0이다. width = 2씩 묶어 확인한다. 3 X 2는 3가지 케이스가 나온다. 즉, dp[2] = 3이다. 3 X 2n(n > 1)을 만족하는 케이스는 다음과 같이 나뉜다. 이전에 나오지 않은 특수 케이스 2가지. 3 X 2m(m = 1...n - 1)의 1번 특수 케이스와 dp[2..

[백준(baekjoon) 2579] 계단 오르기 문제 백준 2579 n개의 계단의 각 점수가 주어진다. 다음과 같은 규칙을 따른 최대 점수를 출력하라. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. (예를 들어 1번 계단을 밟으면 1 -> 2, 1 -> 3 중 하나만 택할 수 있다.) 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 해결 i 번째 계단에서 가능한 상황은 다음과 같다. X O O (= 연속 2번 밟은 경우) 이전 계단에서 첫번째로 밟힌 경우에 자신의 점수를 합산한 것 O X O (= 이전은 밟지 않고, 자신이 첫번째로 밟힌 경우) 전전 계단이 밟힌 값 중 큰 점수에 자신의 점수를 합산한 것 O O ..