백준 닷컴 단계 별로 풀어보기 8단계

1단계 진법 변환

• 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)
• B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.
• 첫째 줄에 B진법 수 N을 10진법으로 출력한다.

import java.util.Scanner;

public class Step_1 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		String str = scan.next();
		int num = scan.nextInt();
		int length =str.length();
		char[] numbers = new char[length];
		for (int i=0; i<length; i++) {
			numbers[i]=str.charAt(i);
		}
		int[] numbers2 = new int[length];
		for (int i=0; i<length; i++) {
			if((numbers[i]+0)>=65&&(numbers[i]+0)<=90) {
				numbers2[i]=numbers[i]-55;
			} else {
				numbers2[i] = numbers[i]-48;
			}
		}
		int sum=0;
		for (int i=0; i<length; i++) {
			int a = (int)(Math.pow(num, length-i-1));
			sum +=(numbers2[i]*a);			
		}
		System.out.println(sum);
	}
}

A.

• b진법 숫자를 문자열로 저장하고, 진법을 나타내는 int num을 저장한다.
• char배열에 b진법 숫자를 분리하여 대입힌다.
• int 배열을 만들고 b진법에 해당하는 숫자로 할당한다.
• b진법을 출력할 sum을 선언하고 0으로 초기화한다.
• 각 자리의 숫자와 진법에 해당하는 숫자를 곱한 값을 sum에 합해준다.
• n진법의 경우 뒤에서 m번째 숫자는 숫자 x n^m-1의 값이 된다.
• 제곱을 표현하기 위해 Math.pow를 이용한다. Math.pow는 double로 값을 반환한다.

2단계 진법 변환 2

• 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다.
• 첫째 줄에 10진법 수 N을 B진법으로 출력한다.

import java.util.Scanner;

public class Step_2 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int num1 = scan.nextInt();
		int num2 = scan.nextInt();

		String re = "";

		int i = num1;
		while (true) {
			if (i % num2 == 0&& i/num2==0) {
				break;
			}
			if (10 <= (i % num2) && (i % num2) <= 36) {
				char char1 = (char) (i % num2 + 55);
				re += char1;
			} else {
				re += (i % num2);
			}
			i = i / num2;
		}
		char[] arr = new char[re.length()];
		for (int j=0; j<re.length(); j++) {
			arr[j]=re.charAt(re.length()-j-1);
		}
		
		re="";
		for (int j=0; j<arr.length; j++) {
			re=re+arr[j];
		}
		System.out.println(re);
	}
}

A.

• 두 수를 int에 받아준다.
• 임시 변수 i를 만들고 while문을 만든다.
• 임시 변수를 진법 b로 나눈 나머지를 해당 문자로 바꾸고 str에 그 값을 받아준다.
• 다음 자리 수를 나타내기 위해서 임시변수를 진법으로 나눈 몫으로 재설정 한다.
• 임시변수가 0이 될 때 까지 반복한다.
• str에 역순으로 된 b진법이 저장되었기 때문에 str을 반대로 바꿔주는 반복문을 만든다.

3단계 세탁소 사장 동혁

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)
• 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

package stage08;

import java.util.Scanner;

public class Step_3 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int test = scan.nextInt();
		int[] arr = new int[test];
		for (int i = 0; i < test; i++) {
			arr[i] = scan.nextInt();
		}
		int quat = 0, dime = 0, nick = 0, penny = 0;
		for (int i = 0; i < test; i++) {
			int temp = arr[i];
			quat = temp / 25;
			temp %= 25;
			dime = temp / 10;
			temp %= 10;
			nick = temp / 5;
			temp %= 5;
			penny = temp;
			System.out.println(quat + " " + dime + " " + nick + " " + penny);
		}

	}
}

A.

• 테스트 수를 int에 받아준다.
• int 배열을 test만큼의 길이로 초기화한다.
• nextInt로 각 배열에 값을 저장한다.
• 쿼터, 다임, 니켈, 페니를 0으로 초기화해 저장한다.
• 반복문을 만들고 임시 변수 temp를 각 배열의 값으로 초기화한다.
• temp를 쿼터, 다임, 니켈, 페니로 나눈 몫을 저장하고, 각 시도마다 temp의 값을 나머지로 지정한다.
• 각 동전의 값을 출력하는 식을 만든다.

4단계 중앙 이동 알고리즘

• 외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.
• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)
• 첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

import java.util.Scanner;

public class Step_4 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int test = scan.nextInt();
		int dotNum = 2;
		for (int i=0; i<test; i++) {
			dotNum=dotNum*2-1;
		}
		System.out.println(dotNum*dotNum);
	}
}

A.

• 각 상태에서 한 변의 점 개수는 기존 값의 2배-1개가 있다.
• 반복문을 통해 n번째 상태의 한 변의 점 개수를 구해주고, 제곱하여 출력한다.

5단계 벌집

• 벌집까지 최소거리를 구하기

import java.util.Scanner;

public class Step_5 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int hex = 1;
		int step = 1;
		while (n > hex) {
			hex += 6*step;
			step++;
		}
		System.out.println(step);
	}
}

A.

• n에 입력 값을 저장한다.
• hex에 기준이 되는 육각형 개수, step에 거리를 지정하고 숫자를 1로 초기화한다.
• hex는 단계마다 6*step만큼 개수가 늘어나는 것을 이용한 반복문을 만든다.
• n이 hex보다 커지는 시점의 step을 출력한다.

6단계 분수 찾기

• 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
• X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

package stage08;

import java.util.Scanner;

public class Step_6 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int div = 1;
		int step = 1;
		while (n > div) {
			div += ++step;
		}
		
		int temp = div-n;
		if(step%2==0) {
		System.out.println((step-temp) + "/" + (temp+1));
		} else {
			System.out.println((temp+1) + "/" + (step-temp));
		}
	}
}

A.

• 지그재그가 일어나는 분수의 단위 개수가 1개 씩 늘어나는 것을 이용하여 div와 step을 반복문으로 지정한다.
• 지그재그가 step마다 방향이 바뀌는 것을 step의 홀짝을 이용해 제어한다.
• step에 따라 분자, 분모의 합이 정해지고, div와 step의 차이를 이용해 분자와 분모의 크기를 정한다.

7단계 달팽이는 올라가고 싶다

• 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
• 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
• 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

import java.util.Scanner;

public class Step_7 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int a = scan.nextInt();
		int b = scan.nextInt();
		int v = scan.nextInt();
		
		int h= v-a;
		int d= h/(a-b)+1;
		if (v==a) {
			d=1;
		} else if(h%(a-b)>0) {
			d++;
		}
		
		System.out.println(d);
	}
}

A.

• 반복문 작성 시 시간 초과 발생, 수학적 접근 필요
• 마지막 날 a만큼 올라갈 수 있는 점을 이용하여 새로운 높이 h를 v-a로 지정
• h를 며칠에 걸쳐 오르는지 체크. h를 a-b로 나누어 계산
• h/(a-b)가 나누어 떨어지면 하루가 덜 걸린다. 나머지 존재 유무를 이용하여 날짜를 조정한다.