[백준 2860번] 종이에 숫자 쓰기 - JAVA 알고리즘

 

2860번

문제
상근이는 종이에 숫자를 쓰려고 한다. 종이에는 1~5 사이의 숫자를 1개만 쓸 수 있고, 상근이는 종이를 무한개 가지고 있다. 열심히 종이에 숫자를 쓴 다음에, 종이에 쓴 숫자의 평균을 P와 같게 만들려고 한다. 이때, 사용한 종이의 개수를 최소로 하려고 한다. P가 주어졌을 때, 각 숫자를 총 몇 번 쓰는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 P가 주어진다. P는 1보다 크거나 같고, 5보다 작거나 같으며 소수점 1자리 ~ 9자리이다.
출력
첫째 줄에 5개의 음이 아닌 정수를 출력한다. 첫 번째 숫자는 1의 개수, 두 번째 숫자는 2의 개수, ..., 마지막 숫자는 5의 개수이다. 가능한 방법이 여러개라면 아무거나 출력한다.
예제 입력	예제 출력
3.321321312	13114677 0 0 1 18135322

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 선언

		//==========1. 입력한 숫자를 받아와 정수와 소수로 나눠준다.==========
		
		StringTokenizer st = new StringTokenizer(br.readLine(),".");
		String integerNum = st.nextToken(); //정수
		String decimalNum = st.nextToken(); //소수
		
		//==========1-1. 끝자리에 0이 들어가있다면 제거해준다.(ex. 4.50 -> 4.5)==========
		int zeroCheck = 0;
		String decimalNum2 = ""; //끝자리 0이 제거된 소수
		
		for(int i = decimalNum.length()-1; i>=0; i--) {//뒤에서부터 쌓기 처음이 0이면 안넣음
			
			if(decimalNum.charAt(i)!='0') {//마지막이 0이 아닐시 쌓기 시작
				zeroCheck=1;
			}
			if(zeroCheck==1) {//오른쪽부터 하나씩 쌓아줌
				decimalNum2 = decimalNum.charAt(i)+decimalNum2;
			}
		}
		
		//==========2. 분자/분모로 변환한다.==========
		
		String numerator = integerNum+decimalNum2; 	//분자
		long numerator2 = Long.parseLong(numerator);//숫자로 변환한 분자(int 길이를 넘어가서 long으로 선언)
		int denominator2 = 1; 						//분모
		for(int i=0; i<decimalNum2.length();i++) {	//분모 자리수만큼 곱해주기
			denominator2 = denominator2 * 10;
		}
		
		//==========3. 분자와 분모의 최대공약수를 구한다.==========
		long big = 0;	//큰수
		long small = 0; //작은수
		
		if(numerator2>denominator2) {//큰수 구하기
			big = numerator2;	
			small = denominator2;
		}else {
			big = denominator2;	
			small = numerator2;
		}
		
		int quotient , remainder , greatest; //목,나머지,최대공약수
		//최대공약수 구하기
		while (true) {
			quotient  = (int) (big / small);
			remainder  = (int) (big - quotient  * small);
			if (remainder  == 0) {
				greatest = (int) small;
				break;
			} else {
				big = small;
				small = remainder ;
			}
		}
		//최대공약수로 나눠준다.
		long numerator3 = numerator2/greatest;		//분자
		long denominator3 = denominator2/greatest;	//분모
		

		//==========4. 출력 값을 계산한다.==========
		long numerator4 = numerator3;
		//1~5의 숫자 (denominator3[분모])개로 (numerator3[분자])를 만들어주면됨..
		int minusNum = 5; 						//1~5중 가장 큰 수인 5부터 뺀다. 
		int[] NumCount = new int[5];
		for(int i = 0; i<denominator3; i++) { 	//분모만큼 반복해야한다.
			
			//분자에서 minusNum을 빼고 남은 수가 분모보다 작으면 안되기때문에 조건을 걸어준다.
			if((denominator3-i-1)<=(numerator4-minusNum)) { 	//(분모-현재순번-1)<=(분자-빼려는 값)
				numerator4 = numerator4-minusNum;
				NumCount[minusNum-1] = NumCount[minusNum-1]+1; 	//숫자별로 얼만큼 사용되었는지 적립한다.(numCount[0]은 1을 사용한 횟수)
			}else {
				minusNum = minusNum -1; 	//더 낮은수로 시도
				i = i - 1; 					//이번 순번 무효
			}	
		}
		
		
		/*//결과 확인용 값 테스트 값 3.321321312
		bw.write("정수:"+integerNum+"\n");
		bw.write("소수:"+decimalNum+"\n");
		bw.write("정리된 소수:"+decimalNum2+"\n");
		bw.write("정리된 분자:"+numerator+"\n");
		bw.write("정리된 분모:"+denominator+"\n");
		bw.write("최대공배수:"+greatest+"\n");
		bw.write("정리된분자:"+numerator3+"\n");
		bw.write("정리된분모:"+denominator3+"\n");
		bw.write("결과 : "+NumCount[0]+" "+NumCount[1]+" "+NumCount[2]+" "+NumCount[3]+" "+NumCount[4]+" "+"\n");
		*/
		bw.write(NumCount[0]+" "+NumCount[1]+" "+NumCount[2]+" "+NumCount[3]+" "+NumCount[4]+"");
		bw.close();
		br.close();
	}
}

 

실행 결과

실행 결과

 

입력값을 받음 (3.20)

토큰으로 정수랑 소수로 나눔(.기준으로 정수 : 3, 소수 : 20)

소수점을 가져와서 마지막이 0이면 지워주는 작업 (소수 : 2) for문 뒤부터 반복

소수점 몇자리인지 체크 (1자리) length

정수와 소수 더하고 10의N제곱 해줌(N은 소수점 자리수  32/10)

32와 10의 최대공약수는 만들어줌 16, 5

1~5 5가지 수로 16을 만들어줌 4,3,3,3,3(여긴 어케하지)
==큰수부터 빼주고 만약 값이 안나오면 뒤로 빼고 적은수 넣기..?
(뺀 결과가 남은 수 보다 커야함) - 1로 채워야하니까

 

브론즈, 실버 티어 문제만 풀다가 골드중 하나정도는 풀 수 있지 않을까? 라는 생각에 풀어보았습니다.

최대 공약수를 만들때 시간초과로 실패했고 재귀함수로 변환해서 해결했습니다.

중간 값 확인을 위해 의미 없는 변수를 중간마다 선언한 부분이 있습니다.

 

개인적으로 정리한 내용을 간단하게 풀어 작성했습니다. 이해가 안가는 부분은 댓글 남겨주시면 설명해드리겠습니다.