최고의 개발자 (목표)

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        /* 유클리드 호제법
        1. a와 b의 최대공약수
        == b와 r의 최대공약수
        == r과 r2의 최대공약수
        ...
        a % b => r
        b % r => r2
        r % r2 => r3
        if) r3가 0, 즉 나머지가 0이면 최대공약수는 r2

        2. a와 b의 최대공배수
        -> a*b / gcd(a,b)
        */

        int T = Integer.parseInt(st.nextToken());

        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int r = gcd(A, B);
            System.out.println(A*B/r);

        }
    }

    public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

풀이

이 문제는 시간제한이 1초이기 때문에 유클리드 호제법을 써야 한다.

유클리드 호제법을 이용해 최대공약수를 구하고, A * B / 최대공약수를 해서 최소공배수를 구했다.

유클리드 호제법은 https://chelim.tistory.com/49 에 따로 설명을 올렸다.

최대공약수란?

A와 B의 공약수 중 가장 큰 수이다. 여기서 공약수란 A의 약수와 B의 약수 중 겹치는 수이다.

예를 들어, 6과 24를 보면 6의 약수는 1,2,3,6이고 24의 약수는 1,2,3,4,6,8,12,24 이다.

즉 공약수는 1,2,3,6이다. 여기서 가장 큰 6이 6과 24의 최대공약수가 된다.

이떄, 24를 6으로 나누면 나머지가 0이다. 

A와 B의 최대공약수를 구하려고 할 떄, A % B = 0 이라면 B가 A, B의 최대공약수가 된다.

유클리드 호제법이란?

자연수 A, B의 최대공약수를 구하는 알고리즘이다.

A % B = R이라고 해보자. 만약 이때 R이 0이라면 B가 최대공약수일 것이다. 0이 아니라면

B % R = R2라고 해보자. 만약 이때 R2가 0이라면 R이 최대공약수일 것이다. 0이 아니라면

R % R2 = R3라고 해보자. 앞 과정을 나머지가 0이 될 때까지 계속 반복해서 최대공약수를 구한다.

예를 들어, 48과 36의 최대공약수를 유클리드 호제법을 이용해서 구해보자.

48 % 36 = 12. 나머지가 0이 아니므로 36과 12의 나머지를 구한다.

36 % 12 = 0. 나머지가 0이다. 즉 48과 36의 최대공약수는 12가 된다.

예를 들어, 16과 10의 최대공약수를 유클리드 호제법을 이용해서 구해보자.

16 % 10 = 6이다. 나머지가 0이 아니므로 10과 6의 나머지를 구한다.

10 % 6 = 4. 나머지가 0이 아니므로 6과 4의 나머지를 구한다.

6 % 4 = 2. 나머지가 0이 아니므로 4와 2의 나머지를 구한다.

4 % 2 = 0. 나머지가 0이다. 2가 최대공약수가 된다.

위의 알고리즘을 코드로 바꿔보자.

public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

앞에서는 a와 b를 나누고, b와 r을 나누고, r과 r2를 나눴다. 즉 a와 b를 나눈 나머지인 r을 구하고 a 자리에 b를, b 자리에 r을 넣어서 다음에는 b % r이 될 수 있도록 한다. while문에서 b가 0인지 0이 아닌지 확인하는 이유도 while문 안에서 조건을 확인하기 전, b자리에 r을 넣었기 때문이다. 만약 b가 0이라면(나머지가 0), a에 b가, b에는 r이 들어있는 상황이기 때문에 원래대로라면 b를 출력해야 맞지만, 현재 b의 값을 가지고 있는 a를 출력해야한다.

최소공배수란?

A와 B의 공배수 중 가장 작은 수이다. 여기서 공배수란 A의 배수와 B의 배수 중 겹치는 수이다.

예를 들어, 48과 36를 보면 48의 배수는 48, 96, 144, 192, 240..이고 36의 배수는 36, 72, 108, 144, .. 이다.

즉 최소공배수는 144이다.

최대공약수와 최소공배수와의 관계

유클리드 호제법에 쓰였던 예시인 48, 36으로 최대공약수와 최소공배수의 관계를 생각해보자.

48과 36의 최소공배수는 144이고, 최대공약수는 12이다.

그럼 144가 48과 36의 최대공약수인 12와 어떤 관계가 있을까?

12는 최대공약수이기 때문에 48과 36의 약수 중 하나이다. 즉 12에 어떤 수를 곱하면 48이 나오고, 12에 어떤 수를 곱하면 36이 나온다. 이때 12 * x = 48, 12 * y = 36이라고 생각해보면, x와 y는 서로소이며 x * y  = 최대공약수이다.

또한 48 * 36 = 12 * 12 * x * y 이다. 이때 양변에 최대공약수를 나눠주면, (48 * 36) / 12 = 12 * 12 이고 , 12 * 12는 144 즉 최소공배수이다. 따라서 A * B / 최대공약수 = 최소공배수 이다. 

위의 유클리드 호제법으로 최대공약수를 먼저 구한뒤, 구한 최대공약수를 이용해 최소공배수를 구할 수 있다.

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] stairs = new int[N+2];
        int[] dp = new int[N+2]; // 계단 1칸이면 밑에 0,1,2 값에서 outofindex

        for(int i = 0; i < N; i++){
            stairs[i] = Integer.parseInt(br.readLine());
        }

        // dp[0] 즉 한 칸 이동에서의 최대는 자기 자신
        dp[0] = stairs[0];
        // dp[1] 은 자기자신과 전칸+자기자신 중 최대
        dp[1] = Math.max(stairs[0]+stairs[1], stairs[1]);
        // dp[2] 는 st[0]+st[2] 또는 st[1]+st[2] 중 최대
        dp[2] =  Math.max(stairs[0]+stairs[2], stairs[1]+stairs[2]);

        for(int i = 3; i < N; i++){
            dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]);
        }
        System.out.println(dp[N-1]);
    }   
}

풀이

문제의 조건을 보고 dp 식을 세워야 한다. 마지막 계단은 무조건 밟아야 한다는 것과, 1칸이나 2칸 이동이 가능하지만 1칸 이동을 연속으로 3번은 불가능하다는 것이다. 즉 1번 계단->2번 계단으로 이동했다면 2번 계단에서는 무조건 4번 계단으로 가는 선택지 밖에 존재하지 않는다.

일단 마지막 계단을 무조건 밟아야 한다는 조건을 생각해보자. 마지막 계단을 n번째 계단이라고 가정하면, n-1번째 계단을 밟고 마지막 계단을 밟는 것과 n-2번째 계단을 밟고 마지막 계단을 밟는 경우가 존재한다. 

이때, n-1번째 계단에서 n번째 계단으로 가는 경우는 더 생각해봐야 하는 것이 있다. n-2번째 -> n-1번째 -> n번째는 조건에 어긋나기 때문에 n-1번째 -> n번째로 가기 위해서는 무조건 n-3번째 -> n-1번째 -> n번째가 되어야한다. 따라서

아래 그림과 같이 최종적으로 2가지 방법을 비교해 총 점수가 더 큰 계단으로 이동해야 한다.

이를 식으로 바꾸면, 왼쪽의 경우는 dp[n-3] + stairs[n-1] + stairs[n] 이 되고, 오른쪽의 경우는 dp[n-2] + stairs[n] 이 된다.

따라서, dp[n] = max(dp[n-3] + stairs[n-1] + stairs[n], dp[n-2] + stairs[n]) 로 구할 수 있다.

dp[0], dp[1], dp[2]는 조건식이 달라서 for문에 들어가기전에 따로 값을 넣어줬고, 계단이 1칸일 때 dp[1], dp[2]에 값을 넣어주는 라인에서 ArrayOutOfIndex 에러가 나기 때문에 dp와 stairs의 크기를 N+2로 지정했다.

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    dp = [0] * 1000001
    dp[1] = 1
    dp[2] = 2

    for i in range(3,N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746
    
    print(dp[N])

풀이

N이 1일 때는 가능한 2진 수열이 1로 총 1개이다.

N이 2일 때는 가능한 2진 수열이 11, 00으로 총 2개이다.

N이 3일 때는 가능한 2진 수열이 111, 100, 001로 총 3개이다.

N이 4일 때는 가능한 2진 수열이 1111, 1100, 1001, 0011, 0000으로 총 5개이다.

N이 5일 때는 가능한 2진 수열이 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001로 총 8개이다.

이를 보면 증가하는 추세가 피보나치 수의 수열과 같다는 것을 알 수 있다.

즉 dp[i] = dp[i-2] + dp[i-1] 임을 알 수 있다.

헷갈리지 않기 위해서 dp[i]의 값을 N이 i일 때 가능한 2진 수열의 길이 % 15746로 정하였다. 즉 index가 0일 때는 사용하지 않았다.

문제

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다. 

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 ≤ A ≤ 23) 와 분 B (0 ≤ B ≤ 59)가 정수로 빈칸을 사이에 두고 순서대로 주어진다. 두 번째 줄에는 요리하는 데 필요한 시간 C (0 ≤ C ≤ 1,000)가 분 단위로 주어진다. 

출력

첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(br.readLine());

        B = B + C;
        
        while(B >= 60){
            A += 1;
            B -= 60;
        }

        while(A >= 24){
            A -= 24;
        }
        
        System.out.printf("%d %d", A, B);
    }
}

풀이

현재 시각에 요리하는데 필요한 시간을 더하면 되는 문제이다. 고려해야할 부분은 A시 B분일 때, A시는 최대 23이고 B는 최대 59라는 것이다. 요리하는데 필요한 시간인 C가 분단위로 주어지기 때문에 B에 C를 더해주고 B가 60이 넘지 않을 때까지 A에 1을 더하고 B에 60씩 빼준다. 즉 B분이 60보다 작아질 때까지 60분을 1시간으로 고치는 것이다.

A시도 최대 23까지 가능하기 때문에 A가 24보다 작아질 때까지 24를 빼준다.