[백준] 일반 수학 1

서론

---

이번에는 일반 수학1 문제를 풀어보았다.

카테고리부터가 일반 수학이다보니, 수학적으로 생각해야할 문제가 많았던 것 같다!.

고민을 많이 해보게 된 카테고리 인데, 내가 푼 방식이 맞았을 때 쾌감이 있었다!.

---

2745 : 진법 변환

---

문제

---

https://www.acmicpc.net/problem/2745

2745번: 진법 변환

이 문제는 B진법 수를 10진법으로 바꾸는 문제이다.

---

해설

---

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());

        long result = 0;

        String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        String N = st.nextToken();
        int B = Integer.parseInt(st.nextToken());
        for (int i = N.length()-1; i >= 0; i--) {
            int tmp = N.charAt(i);
            if(alpha.contains(String.valueOf(N.charAt(i)))){
                tmp -= 55;
            }
            else {
                tmp = Integer.parseInt(String.valueOf(N.charAt(i)));
            }
            result += (tmp * Math.pow(B, (N.length()-1) - i));
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}

내가 생각한 방식은 예시 입력을 이용하면 
ZZZZZ는 36 * 36^0 + 36 * 36^1 + 36 * 36^2 + 36 * 36^3 + 36 * 36^4 이므로 이를 일반화하여 코드를 작성하였다.

이때 10부터는 알파벳으로 입력되므로 이를 A의 아스키코드 65 - 55 = 10으로 설정하여 계산해준다.

하지만 더 쉬운 방법이 있었다..

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());

        String N = st.nextToken();
        int B = Integer.parseInt(st.nextToken());
        long result = Integer.parseInt(N,B);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}

Integer.parseInt()를 항상 매개변수 1개만 이용하여 사용하였었는데, 매개변수가 2개일 때는 생각도 하지 못했다..

Integer.parseInt(String s, int radix) 로, 문자열 s를 radix진법으로 만들어준다고 한다!.

---

11005 : 진법 변환2

---

문제

---

https://www.acmicpc.net/problem/11005

11005번: 진법 변환 2

이 문제는 위 문제의 반대이다, 10진법 수를 입력받고 이를 B진법으로 바꿔야한다.

10진법을 B진법으로 변환하려면, N을 B로 나누어 몫과 나머지를 구하고, 몫이 더이상 나누어지지 않을때 까지 반복한 후, 

나머지를 밑에서 부터 읽어들이는 방식을 사용하여 해당 문제를 해결하였다.

---

해설

---

이런 식으로 10진법 7은 2진법 111이다.

이를 구현하면

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());

        long N = Long.parseLong(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        String result = "";
        while (N > 0){
            int mod = (int) (N % B);
            N /= B;
            if(mod > 9){
                mod += 55;
                result += (char) mod;
            }
            else {
                result += String.valueOf(mod);
            }
        }
        StringBuilder sb = new StringBuilder(result);
        sb.reverse();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

이렇게 되는데, 뒤에서 부터 읽기 위해 StringBuilder의 reverse()를 사용하였다!.

하지만 이 문제도 더 간단한 방법이 있어따..ㅋㅋㅋㅋㅋㅋ..

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 N = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
        
        StringBuilder sb = new StringBuilder(Integer.toString(N,B).toUpperCase());
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

Interget.toString(N,B)를 통해 10진법 수 N을 B진법으로 변환한 후 String으로 반환한다!.

정말 간단하고 쉬워보인다..

---

2720 : 세탁소 사장 동혁

---

문제

---

https://www.acmicpc.net/problem/2720

2720번: 세탁소 사장 동혁

이 문제는 간단하게 거스름돈의 개수를 구하는 문제이다.

---

해설

---

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));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            int C = Integer.parseInt(br.readLine());
            sb.append(C / 25).append(" ");
            C %= 25;
            sb.append(C / 10).append(" ");
            C %= 10;
            sb.append(C / 5).append(" ");
            C %= 5;
            sb.append(C).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

간단하게 풀었따!.

---

2903 : 중앙 이동 알고리즘

---

문제

---

https://www.acmicpc.net/problem/2903

2903번: 중앙 이동 알고리즘

이 문제는 정사각형의 점을 구하는 문제이다!.

---

해설

---

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));

        int N = Integer.parseInt(br.readLine());
        int result = 2;
        for (int i = 0; i < N; i++) {
            result = result * 2 - 1;
        }
        bw.write(String.valueOf((int)Math.pow(result, 2)));
        bw.flush();
        bw.close();
    }
}

이 문제를 보고 패턴을 찾아야 한다고 생각하고 이를 풀어보았다.

먼저 사각형이 아닌 줄별로 패턴을 찾아본 결과 2 -> 3 -> 5 -> 9 로 각 줄의 점 개수가 증가하는 것을 알 수 있었다.

이를 식으로 만들면 result = result * 2 - 1이며 사각형에 포함된 점의 개수는 해당 결과의 제곱이므로,

쉽게 해결할 수 있었다.

---

2292 : 벌집

---

문제

---

https://www.acmicpc.net/problem/2292

2292번: 벌집

이 문제는 N번째 벌집에 가려면 몇개의 벌집을 지나야 하는지 구하는 문제이다.

조금 고민해보았던 문제다!.

---

해설

---

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));

        int N = Integer.parseInt(br.readLine());

        int cnt = 1;
        int way = 1;
        while (true){
            if(cnt >= N){
                bw.write(String.valueOf(way));
                break;
            }

            way++;
            cnt += (6 * way) - 6;
        }
        bw.flush();
        bw.close();
    }
}

이 문제를 풀기 위해서 마찬가지로 패턴을 찾아 보기로 했다.

여기서 패턴은 1번을 way1, 2~7번을 way2 이런식으로 둔다면, 각 way에 포함되는 벌집의 개수는 6 * n - 6임을 알아낼 수 있었다.

cnt는 해당 way에 포함된 벌집의 개수를 의미하며, N번째 벌집에 도달하기 위한 횟수를 way라고 한다.

그렇다면, N번째 벌집에 도달하기 위해서 way를 증가시키며 해당 way에 포함될 수 있는 벌집의 개수 cnt보다 N이 작을 때 way를 출력하게 되면, 해당 way가 N번째 벌집에 도달하기 위해 지나야할 벌집의 개수이다.

패턴을 찾아내는 부분에서 조금 고민이 필요했던 문제였다!

---

1193 : 분수찾기

---

문제

---

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

이 문제도 역시 패턴을 찾는데 시간이 조금 걸렸던 문제이다.

또한, 메모리 제한에 걸렸었다!.

---

해설

---

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));

        int X = Integer.parseInt(br.readLine());
        int cnt = 1;
        int num = 2;
        int a = 1;
        int b = 1;

        while (cnt < X){
            for (int j = 0; j < num; j++) {
                if (num % 2 == 0){
                    a = j+1;
                    b = num-j;
                }
                else {
                    a = num-j;
                    b = j+1;
                }
                cnt++;
                if(cnt >= X){
                    break;
                }
            }
            num++;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(a).append("/").append(b);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

처음에는 이 문제를 ArrayList에 각 분자와 분모를 저장해두었는데, 메모리 제한에 걸리게 되었다.

그리고 나서 생각해보니 굳이 N번째 분수를 구하기 위해서 1~N-1개의 분수가 필요하지 않다는 것을 알았다.

따라서 1/1을 1번 이라하면, 1/2, 2/1는 2번 ...이런 식으로 확장이 가능하다.

그런데 이때 패턴을 보면, 짝수번일때 분모는 1부터 증가, 분자는 1까지 감소 하는 것을 확인할 수 있다.

반대의 경우에는 분자와 분모가 반대로 증가, 감소한다!.

따라서 두개의 경우를 나누고, cnt는 현재까지 구한 개수로 X보다 크거나 같으면 반복문을 종료하고 분자와 분모를 출력한다.

패턴을 찾는데 오래 걸려서 조금 힘들어따./

---

2869 : 달팽이는 올라가고 싶다

---

문제

---

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

이 문제는 처음에는 정말 간단하게 생각해서 풀었지만, 실패했다.

---

해설

---

처음 이 문제를 접했을 때는 그냥 반복문을 통해 이동하는 거리 A만큼 더하고, 목표보다 크면 종료하고 작으면 B만큼 빼면 된다고 생각하였다.

하지만 반복문을 사용하게 되니 큰 수가 테스트로 주어지면 시간초과가 나와서 실패하였다.

 

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 A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        int check = (V - A) % (A - B);
        int day = 0;
        if(check != 0){
            day = (V - A) / (A - B) + 2;
        }
        else {
            day = (V - A) / (A - B) + 1;
        }
        bw.write(String.valueOf(day));
        bw.flush();
        bw.close();
    }
}

따라서 이 문제도 여러 테스트 상황을 통해 식을 구해보기로 하였다.

가장 먼저 생각했던 것은 V / A-B 였는데 이렇게 되면,

만약 V = 15, A = 5, B = 3이면,  15 / 2 == 7이다, 나머지가 있으므로, 1일을 더한다고 간단하게 생각했는데, 이는 틀렸다.

실제 답은 6일로, 간과한 부분은 5일째까지 2만큼씩 이동하지만 마지막날 5만큼 이동하게 된다면 도착한 것이기 때문이다.

따라서 (V-A) / (A-B)일이 기본적으로 필요하고, 여기에 나머지가 존재한다면, 다음날 + A 만큼 이동하여도 도착하지 못하기 때문에 2일, 나머지가 없다면 + A 만큼 이동하면 도착지이기 때문에 두가지 경우로 나누어준다.! 

---

10757 : 큰 수 A + B

---

문제

---

https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

이 문제는 A + B이지만 매우 큰 수이다.

---

해설

---

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        BigInteger A = new BigInteger(st.nextToken());
        BigInteger B = new BigInteger(st.nextToken());

        bw.write(String.valueOf(A.add(B)));
        bw.flush();
        bw.close();
    }
}

문제를 해결하기 위해 BigInteger를 사용하였다.

다른 방법을 사용한다면, String으로 읽어서 이를 각 자리수 별로 더해주는 방식을 사용해야할 것 같다.!

---

결론

---

카테고리가 일반 수학 1이였다 보니, 패턴을 찾아 수식으로 만들고 이를 구현하는 문제가 많았던 것 같다.

패턴을 찾는 과정에서 맞다고 생각했던 부분이 틀리기도 하고, 패턴이 잘 보이지 않는 문제도 있었는데,

결국 다 풀어서 매우 뿌듯하면서도, 몰랐던 부분도 있어서 아직 많이 부족하다고 느꼈다!

화이팅ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ.

---