백준/단계별로 풀어보기
백준 - 단계별로 풀어보기 - JAVA (7단계 : 기본 수학 1 / 8문제) (2022.12.26 월)
MoveForward
2022. 12. 26. 04:02
1단계 : 1712번 / 손익분기점
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
long count = 0;
if(B>=C) {count = -1;}
else {
while( (A+B*count) >= C*count ){
count ++;
}
}
System.out.println(count);
}
}2단계 : 2292번 / 벌집
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a = (N - 2) / 6;
int count = 1; // N = 1인 경우로 초기화
for(int i=1; i<N; i++){
if(a - i < 0){
count = i + 1;
break;
} else {a = a - i;}
}
System.out.println(count);
}
}| 벌집 방 호수 | 지나는 방의 개수 | 증가 추이 |
| 1 | 1개 | 제외 |
| 2~7 | 6개 | 제외 |
| 8~19 | 12개 | +6 |
| 20~37 | 18개 | +6 |
| 38~61 | 24개 | +6 |
3단계 : 1193번 / 분수찾기
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int a=1; int b=1; int k = 1;
for(int i=1; i<X; i++){
if (X - i > 0){
X = X - i;
}
else {
break;
}
k = i + 1;
}
if (k%2 == 0){
b = k;
for(int i=1; i<X; i++){
a++; b--;
}
} else {
a = k;
for(int i=1; i<X; i++){
a--; b++;
}
}
System.out.println(a+"/"+b);
}
}* 주어진 X값을 -1, -2, -3, -4 , ... ,-i 순서대로 중첩 계산하여 나온 X값이 짝수일 경우 좌표 (1, i) 부터 (+1, -1)을 X-1번 계산하고, X값이 홀수인 경우 좌표 (i, 1) 부터 (-1, +1)을 X-1번 계산하여 정답 좌표를 도출하는 방식.
4단계 : 2869번 / 달팽이는 올라가고 싶다
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; int Day = 0;
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
if ((V - A)%(A - B) > 0){
Day = (V - A)/(A - B) + 2;
} else {
Day = (V - A)/(A - B) + 1;
}
System.out.println(Day);
}
}** 실행 시간을 줄이기 위해서 Buffer를 사용한 입출력 사용
** 막대를 완등한 시점은 달팽이가 막대를 오르는 시간인 '낮'시간 인 것이 중요
5단계 : 10250번 / ACM 호텔
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // test 개수
for(int i=0; i<T; i++){
int H = sc.nextInt(); // 호텔 층 수
int W = sc.nextInt(); // 각층 방 개수
int N = sc.nextInt(); // 손님 번호
int roomNum = 0; int a = N % H;
if (N % H == 0) {a = H;}
roomNum = (a) * 100 + ( ((N-1) / H) + 1);
System.out.println(roomNum);
}
}
}6단계 : 2275번 / 부녀회장이 될테야
import java.util.Scanner;
public class Main{
// DP 이용
public static int[][] check = new int[15][15];
public static int MemderNum(int x, int y){
// check에 이미 값이 저장되있는 경우
if(check[x][y] != 0){
return check[x][y];
} else {
if (x == 0){
check[x][y] = y;
} else {
for (int a=1; a<=y; a++){
check[x][y] += MemderNum(x-1, a);
}
}
return check[x][y];
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // test 개수
for (int i=0; i<T; i++){
int k = sc.nextInt();
int n = sc.nextInt();
System.out.println(MemderNum(k, n));
}
}
}** (k, n) = (k-1, 1) + .... + (k-1, n) 형식의 점화식을 도출하자마자 동적 프로그래밍(DP)가 떠오르게 되었다.
DP의 핵심은 한번 구했던 것은 다시 구하지 않고 메모한것을 불러오는 것인 "Memoization 기법" 임을 명심하자 .
[관련 게시물]
https://notorious.tistory.com/62
[알고리즘] Dynamic Programming
1. Dynamic Programming (동적 계획법) 이란? : 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는
notorious.tistory.com
7단계 : 2839번 / 설탕 배달
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int tNum = 0; // 3kg 개수
int fNum = 0; // 5kg 개수
int total = tNum + fNum;
fNum = N / 5;
if (N % 5 == 0){// 5kg으로 다 나누어지는 경우
total = fNum + tNum;
}
else if ( (N % 5 == 1) || (N % 5 == 4)){
if (fNum > 0){
fNum = fNum - 1;
tNum = ((N % 5) + 5) / 3;
total = fNum + tNum;
} else {total = -1;}
}
else if( (N % 5 == 2) ){
if (fNum > 1){
fNum = fNum - 2;
tNum = ((N % 5) + 10) / 3;
total = fNum + tNum;
} else {total = -1;}
}
else{ // (N % 5 == 3)
tNum = (N % 5) / 3;
total = fNum + tNum;
}
System.out.println(total);
}
}1) 최대한 5kg 으로 충당
2) 남은 중량 3kg로 나누어 지지 않는 경우 5kg 내려 받음
3) 5kg 포대로 나누고 난 후 남은 중량 1, 2, 3, 4에 대한 경우의 수 고려
| (5kg으로 충당 후) 남은 중량 | 5kg 한개 내려받음 (5kg 포대 -1) | 5kg 두개 내려받음 (5kg 포대 -2) | 전제조건 |
| 1kg | 6kg (3kg 포대 두개로 치환) | X | 5kg 포대 개수 >= 1 |
| 2kg | 7kg | 12kg (3kg 포대 네개로 치환) | 5kg 포대 개수 >= 2 |
| 3kg (3kg 포대 하나로 치환) | X | X | X |
| 4kg | 9kg (3kg 포대 세개로 치환) | X | 5kg 포대 개수 >= 1 |
8단계 : 10757번 / 큰 수 A+B
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
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(), " ");
BigInteger A = new BigInteger(st.nextToken());
BigInteger B = new BigInteger(st.nextToken());
A = A.add(B);
System.out.println(A.toString());
}
}BufferedReader와 BigInteger 라이브러리를 사용하여 해결하였다.
이 방법 이외에도 많은 방법이 존재한다.