1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어떨어진다.
따라서, 최대공약수는 21이다.
최소 공배수는 1071*1029 / 두수의 최대 공약수 이다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int gcd = GCD(p,q);
bw.write(gcd+"\n"+(p*q)/gcd);
bw.close();
}
static int GCD(int p, int q)
{
if(p < q){
int tmp = p;
p = q;
q = tmp;
}
if(q == 0)
return p;
return GCD(q,p%q);
}
}
우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.
하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.
메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화 하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다
현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.
입력
입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다
단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.
출력
필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.
풀이
DP를 이용해야 하고, M 바이트 보다 큰 것들 중 가장 작은 비용을 고르는 문제 이므로 배낭 문제와 비슷 함을 알 수 있음.
접근 방식은 아래 래퍼런스에 있는 블로그를 참조해서 풀었습니다.
모든 비용의 합을 최대 배열로 두고, 각각의 비용에 최대로 들어갈 수 있는 메모리의 크기를 구합니다.
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 bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] run,memory,dp;
run = new int[N];
memory = new int[N];
st = new StringTokenizer(bf.readLine());
int sum = 0;
StringTokenizer st2 = new StringTokenizer(bf.readLine());
for (int i = 0; i < N; i++) {
run[i] = Integer.parseInt(st.nextToken());
memory[i] = Integer.parseInt(st2.nextToken());
sum += memory[i];
}
dp = new int[sum+1];
for (int i = 0; i < N; i++) {
for (int j = sum; j >= memory[i]; j--)
dp[j] = Math.max(dp[j], dp[j-memory[i]]+run[i]);
}
for (int i = 0; i <= sum; i++) {
if(dp[i] >= M) {
System.out.println(i);
break;
}
}
}
}
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.
규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.
N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.
접근 방법
1. N, M, K의 범위를 봤을 때 100,100, 10억이고, N,M개의 같은 것이 있는 수열임을 볼 때 DP문제임을 알 수 있다.
2. 문자 A,Z가 N개 M개로 만들 수 있는 개수는 A,Z 가 N-1,M개와 N,M-1개로 만들 수 있는 개수의 합과 같다.
3. 이를 통해 K와 N+M개로 만들 수 있는 수를 비교 하면서 앞에서 부터 A인지 Z인지 하나씩 만들면서 정답을 도출한다.
국제대학소포센터(ICPC: International Collegiate Parcel Center)는 전세계 대학생들을 대상으로 소포 무료 배송 이벤트를 진행하고 있다. 무료 배송 조건은 보낼 소포가 물품 4개로 구성되어야 하며 이들 물품의 무게 합이 정확히 정해진 정수 무게w그램이어야 한다는 것이다.
부산대학교에 있는 찬수는 영국 왕립대학에 있는 수환에게 보낼 물품이 매우 많이 있는데, 각 물품의 무게(모두 정수 그램)는 모두 다르다. 이 이벤트는 한시적으로 진행되는 이벤트이기 때문에 찬수는 자신이 보낼 물품 중에서 이 조건을 만족하는 물품 4개가 있는지 가능하면 빨리 알아내고 싶다. 다시 말해서 서로 다른n(n≥ 4)개의 정수로 이루어진 집합A에서 4개의 원소만 꺼내어 만든 부분집합B(|B| = 4)가 ∑b∈Bb=w조건을 만족하는지 판단하려고 한다.
주어진w와A에 대해서, 위 조건을 만족하는 부분집합B가 존재하면 YES를, 아니면 NO를 출력하는 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게w(10 ≤w≤ 799,994)와A의 원소 개수n(4 ≤n≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는A의 원소인n개의 정수ai∈A(1 ≤i≤n)가 공백으로 분리되어 주어진다. 각 원소ai는 1이상 200,000이하이다(1 ≤ai≤ 200,000).
출력
출력은 표준출력을 사용한다. 문제의 조건에 따라YES나NO를 한 줄에 출력한다.
접근 방법
일단 이 문제는 시간 제한이 1초이고, 원소 개수가 5,000개 까지 들어올 수 있으므로 일반적인 조합으로 풀면 시간이 초과하게 된다.
입력받은 수 중에 4개의 합이 w가 되면 되므로 중복으로 계산이 되어야 한다 -> 이를 통해 DP문제 임을 깨달았다.
점화식을 구해야 하는데 먼저 입력 받은 무게를 정렬을 한 뒤 무게를 더해 가는데 4개를 2개 2개로 나뉘면 연산의 횟수가 줄어들어 이를 이용한다.
앞에서 부터 2개를 더한 값을 인덱스로 사용하고, 그 배열에는 무게가 무거운 인덱스를 넣는다. 그리고 그 더한 값을 W에서 빼준 값의 인덱스를 가진 DP가 존재하는지 확인을 하고, 그 인덱스가 2개 더한 값 중 무거운 인덱스보다 크기가 크면 값을 가지게 된다.
이 이유는 2중 포문이 순서대로 돌아가므로 DP배열에 들어 있는 것이 무거운 것만 있어도 중복이 되지 않음을 알 수 있다.
예시의 경우 i가 2일때 weigth[i][6] = 10 이고, w-10인 dp[11] 에 7이 들어 있으므로 이미 값이 있다는 것은 이전에 만들어 졌다는 것을 의미 하며, 현재 들어있는 7이 6보다 큰 값이므로 dp[11] 은 7번 인덱스와 1번 인덱스, dp[10]은 2번 인덱스와 6번 인덱스 임을 알 수 있다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int w,n;
w = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int[] weight = new int[n];
int[] dp = new int[799994 + 1];
st = new StringTokenizer(bf.readLine());
for (int i = 0; i < n; i++)
weight[i] = Integer.parseInt(st.nextToken());
Arrays.sort(weight);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n ; j++) {
int tmp = weight[i]+weight[j];
if(tmp > w)
continue;
dp[tmp] = j;
if(dp[w-tmp]!= 0 && dp[w-tmp] > j){
System.out.println("YES");
return;
}
}
}
System.out.println("NO");
}
}
한 생물학자가 새로 발견된 짚신벌레 종의 생태에 대해 연구하고 있다. 매우 번식력이 강하다고 알려진 이 종은 아래와 같은 특징을 가지고 있다.
무성 생식을 한다.
태어난 이후 a일째 되는 날 성체가 된다.
성체가 된 날부터 매일 한 마리씩 새로운 개체를 만들어낸다: 성체가 되자마자 첫 개체를 만들어내고, 그 이후로 하루가 지날 때마다 새로운 개체를 하나씩 만들어낸다. 새로운 개체 역시 태어난 이후로 a일째 되는 날부터 성체가 되어 새로운 개체를 만든다.
태어난 이후로 b일째 되는 순간부터는 새로운 개체를 더 이상 만들지 않는다. 태어난 지 a일째 날부터 b일째 되는 날의 전날까지 새로운 개체를 만들어내므로 일생동안 총 b-a 마리의 개체를 만들어낸다.
태어난 이후로 d일째 되는 순간 죽는다.
아래는 a=2, b=4, d=6일 때 수조에 새로 태어난 짚신벌레 한 마리를 넣고 매일 관찰한 결과를 기록한 것이다. 괄호 안의 숫자들은 수조 안의 짚신벌레들이 각각 태어난 이후 며칠이 되었는지를 나타내는 정수이다.
태어난 날: (0) - 새로운 개체를 집어넣음
1일째 되는 날: (1) - 짚신벌레가 자람
2일째 되는 날: (2, 0) - 짚신벌레가 태어난 지 2일째가 되므로 성체가 되고 새 개체를 만들어 냄
3일째 되는 날: (3, 1, 0) - 2일째 성체가 된 짚신벌레가 오늘도 새 개체를 하나 만들어 냄
4일 째 되는 날: (4, 2, 1, 0) - 2일째 되는 날 만들어진 짚신벌레가 새로운 개체를 만들어 냄 (처음에 넣은 짚신벌레는 새 개체를 만들어내지 못함)
5일 째 되는 날: (5, 3, 2, 1, 0, 0)
6일 째 되는 날: (4, 3, 2, 1, 1, 0, 0) - 처음에 넣은 개체는 죽는다.
6일 째 되는 날 수조안에 살아있는 짚신벌레는 총 7마리가 된다.
짚신벌레의 번식 정보 a, b, d에 대하여, 새로 태어난 짚신벌레 한 마리를 수조 안에 넣은 이후 N일째 되는 날 살아있는 짚신벌레 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다.
출력
첫째 줄에, 수조에 짚신벌레 한 마리를 넣은 지 N일째 되는 날 수조에 살아 있는 짚신벌레의 수를 1000으로 나눈 나머지를 출력한다.
풀이
a일 부터 무성생식이 가능하므로 a까지는 1마리로 유지된다. 이후로 b일까지 생식을 진행하므로 계속 증가한다. 이때 b일 전까지의 벌레의 마리수는 전날 + 오늘 새로 태어난 벌레의 수이다. 그래서 dp[i] = dp[i-1] + dp[i-a] 이다.
오늘 태어난 벌레의 수는 오늘 부터 a일 전에 있던 벌레의 수이다.
하지만 b일 이후에는 더이상 생식을 하지 않기에 b일 이후의 벌레는 dp[i] = dp[i - 1] + dp[i - a] - dp[i - b] 이다. 이렇듯 더이상 생식을 하지 않은 벌레 수를 빼주면서 더해간다.
그리고 d일 이후에는 죽은 벌레의 수를 빼주면 된다.
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 bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int death = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[] dp = new int[N+1];
dp[0] = 1;
for (int i = 1; i <= N; i++) {
if (i<start) // 시작날 전까지 유지됨.
dp[i] = dp[i-1]%1000;
else if(i<end) // 단순하게 증가함! 전날 + 새로 태어남
dp[i] = (dp[i-1] + dp[i-start])%1000;
else
dp[i] = (dp[i-1]+dp[i-start]-dp[i-end]+1000)%1000;
}
if(N-death>=0)
System.out.println((dp[N]-dp[N-death]+1000)%1000);
else System.out.println(dp[N]%1000);
}
}
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
풀이
이 문제는 DP문제로 시간이 1초임을 유의해서 풀어야 한다.
단순한 아이디어로 풀수 있는 문제이다.
왼쪽 끝과 오른쪽 끝은 내려갈 수 있는 곳이 2곳으로 한정되어 있고, 중간은 세 곳 모두 갈 수 있으므로 연산을 최대와 최소만 찾아서 구해주면 답은 나온다.
괜히 이 방법이 아닐까봐 다른 방법을 생각해보다가 시간이 오래 걸렸다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
StringTokenizer st = new StringTokenizer(bf.readLine());
int[] input = new int[3];
int[][] dp = new int[N][6];
for (int i = 0; i < 3; i++)
input[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < 3; i++)
dp[0][3 + i] = dp[0][i] = input[i];
for (int k = 1; k < N; k++) {
st = new StringTokenizer(bf.readLine());
for (int j = 0; j < 3; j++)
input[j] = Integer.parseInt(st.nextToken());
int i = k-1;
dp[k][0] = Integer.min(dp[i][0], dp[i][1]) + input[0];
dp[k][1] = Integer.min(dp[i][0], Integer.min(dp[i][1], dp[i][2])) + input[1];
dp[k][2] = Integer.min(dp[i][1], dp[i][2]) + input[2];
dp[k][3] = Integer.max(dp[i][3], dp[i][4]) + input[0];
dp[k][4] = Integer.max(dp[i][3], Integer.max(dp[i][4], dp[i][5])) + input[1];
dp[k][5] = Integer.max(dp[i][4], dp[i][5]) + input[2];
}
Arrays.sort(dp[N-1]);
System.out.printf("%d %d",dp[N-1][5],dp[N-1][0]);
}
}
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.
입력
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.
출력
M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.
풀이.
이 문제는 Segment-Tree와 관련된 문제이다. 기본 세그먼트 트리를 기반으로 했을 때 주요 문제의 포인트는 단말 노드가 아닌 노드들은 모두 가장 작은 값을 올려 두는 것이다. 이를 제외한다면 기본 세그먼트 트리의 기본문제와 동일하다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static long[] arr,tree;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new long[N+1];
tree = new long[4*N];
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(bf.readLine());
initTree(0,N-1,1);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
bw.write(searchTree(0,N-1,1,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1)+"\n");
}
bw.close();
}
public static long initTree(int start, int end, int index){//세그먼트 트리를 만드는 함수
if(start == end)
return tree[index] = arr[start];
else{
int mid = (start+end)/2;
return tree[index] = Long.min(initTree(start,mid,index*2), initTree(mid+1,end,index*2+1));
}
}
public static long searchTree(int start, int end, int index, int left, int right){
//세그먼트 트리 탐색 함수
if(start > right || end < left)
return Integer.MAX_VALUE;
if(start>=left && end <= right)
return tree[index];
int mid = (start + end)/2;
return Long.min(searchTree(start,mid,index*2,left,right), searchTree(mid+1,end,index*2+1,left,right));
}
}
