백준 단계별 풀이 - 일반 수학1

https://www.acmicpc.net/step/8

일반 수학 1 단계

오늘은 일반 수학1을 단계별 문제로 풀었다. 

일반 수학1 총 7문제를 풀었다.

이번에는 진법에 대한 문제들이 많이 나왔다. 

풀었던 문제중에서 인상깊었던 문제 몇 개를 적어본다.

 

 

 

 

 

 

 

 

백준 11005 - 진법 변환 2

---

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

11005번: 진법 변환 2

 

 

 

문제분석

---

 

요약하자면, 10진법 수 N을  B진법으로 바꾸는 문제이다. 

 

10을 넘는 숫자는 보통 알파벳으로 표현한다. 

그러므로 10보다 작으면 숫자, 10이상이면, 알파벳으로 표현하도록 한다.

입력받은 숫자 N을 적용할 진법 B로 계속 나누면서, 나머지가 10보다 작으면  '0'을 더해서 숫자를 표현하게 하고, 그외에는 10보다 크니까, 'A'를 더해서 알파벳으로 표현한다. 이후 list에 넣어서 역순으로 출력하면 된다. 

 

 

 

 

정답

---

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

// 11005번 진법 변환2
public class boj_1_11005 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        List<Character> list = new ArrayList<>();
        while (n > 0) {
            if (n % b < 10) {
                list.add((char) (n % b + '0'));
            }
            else{
                list.add((char) (n % b - 10 + 'A'));
            }

            n /= b;
        }

        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.print(list.get(i));
        }

    }
}

 

 

 

 

 

 

 

 

 

 

 

백준 2869 - 달팽이는 올라가고 싶어 

---

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

11005번: 진법 변환 2

 

 

 

문제분석

---

요약하자면,

달팽이가 하루에 낮에 A를 올라가고, 밤에 B를 내려간다. 몇일이 걸리는가? 

 

처음에 문제를 보았을 때는.... 너무 쉬운 문제라고 생각했다. 

단순하게 (A - B) x 일수를 하다보면 결과가 나올 것이라고 생각했다.

하지만 여기에는 조건이 붙어있다. "정상에 올라간 후에는 미끄러지지 않는다는 것" 이다.

한마디로 하루에 4미터 오르고 2미터를 내려오고 10미터 막대기를 올라간다고 했을 때, (4 - 2) x 5로 5일이 걸리는게 아니라, 1일 (4 > 2), 2일 (6 > 4), 3일 (8  > 6), 4일 (10 > 종료) 이렇게 4일만에 올라가버리고 만다. 

그래서 이를 잘 고려해서 문제를 풀어야한다.

 

추가적으로 1,000,000,000 까지의 값이 입력으로 들어오므로 반복문 보다는 수식으로 빠르게 풀어야 한다. 

 

수식을 생각해본다. 

(V - B -1) / (A - B) +1

도착하면, 미끄러지지 않으므로 미끄러지는 상황을 제외한,  (V-B)에 도달하면 도착한 것으로 한다. 이렇게 하면, 마지막날 내려간 날까지를 포함하게 되므로 (V-B-1)로 한다. 이 값을 하루에 움직이는 거리 (A - B)로 나눈다. 목표 지점에 도달했을 때 더 이상 내려가지 않아도 되기 때문에 +1을 해준다. 

예를들어, 4를 올라가고 2를 내려가고 10의 거리를 올라가야한다. 여기서, (V - B - 1) / (A - B) 를 한다면, 3.5일이 나온다. 중간에 멈춘 값이다. 그래서 도착했을 때의 값을 위해 1을 더해주는 것이다. 

 

 

 

 

 

 

정답

---

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 V = Integer.parseInt(st.nextToken());

        int days = (V - B - 1) / (A - B) + 1; // 수식을 이용하여 일 수 계산

        System.out.println(days);
        br.close();
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

백준 2903 - 중앙 이동 알고리즘

---

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

2903번: 중앙 이동 알고리즘

 

 

 

문제분석

---

 

 

 

문제를 처음 봤을 때는, 이게 뭐야..? 라고 생각했다,

점 사이에 상하좌우, 중앙에 점이 추가되고.. .반복한다...이 과정을 거치고 점 몇개가 존재하는가에 대한 문제이다.

 

하지만 어렵게 생각할 필요가 없었다. 

시작점이 4개, 다음이 9개, 25개, 81개.... 숫자에만 집중을 해보면 일정한 규칙이 있다는 것을 알 수 있다.

이 값들은 제곱수이다. 이 값들의 제곱근을 구해보면, 2, 3, 5, 9, 17 의 규칙이 있고 여기에는 1, 2, 4, 8 을 더하는 규칙이 있다. 정리해보면,  (2^n +1)이 제곱근의 규칙이 된다. 이 값을 다시 제곱하면 점의 갯수를 구할 수 있다.

 

 

 

 

정답

---

 

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());
		br.close();
         
        System.out.println((int)Math.pow(Math.pow(2, n) +1, 2));
    }
}

수식을 이용해서 간단하게 출력할 수 있다. 

Math.pow로 제곱을 할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

백준 2292 - 벌집

---

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

2292번: 벌집

 

 

 

문제분석

---

 

 

문제를 요약하자면, 벌집이 그림과 같이 이루어져 있다.

"중앙 방에서 원하는 번호의 방을 가려면 몇번을 거쳐서 가야 하는가?" 이다.

 

이 문제도 위의 점 갯수 문제와 같이 수식을 만들어 풀면 된다.

1번방 주변에는 6개의 방이 생긴다. 6개의 방 주변에는 12개의 방이 생긴다. 12개의 방 주변에는 18개의 방이 생긴다...

그러므로 몇개의 방을 지나야 한다고 하면, 이렇게 범위를 정해서 1개씩 더하도록 하면 된다.

 

 

 

 

 

정답

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int roomNumber = scanner.nextInt();
        scanner.close();

        int count = 1; // 이동 횟수
        int range = 1; // 범위 (현재 방 주변에 있는 방의 최대 번호)

        if (roomNumber == 1) {
            System.out.println(1); // 중앙 방의 경우
        } else {
            while (roomNumber > range) {
                range += 6 * count; // 방 번호 범위 업데이트 (6의 배수로 증가)
                count++; // 이동 횟수 증가
            }
            System.out.println(count);
        }
    }
}

count를 이동 횟수라고 한다. 

방 번호가 범위보다 커질 때까지 반복한다.

범위는 6의 배수만큼 계속 더해진다. 해당 범위를 지나치면 count를 1 증가시킨다.