백준 - 단계별로 풀어보기 - JAVA (7단계 : 기본 수학 1 / 8문제) (2022.12.26 월)

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

---

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 라이브러리를 사용하여 해결하였다.

이 방법 이외에도 많은 방법이 존재한다.

---