[백준] 2231번 : 분해합 - JAVA[자바] - 티스토리

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

2231번: 분해합

*문제는 위에서 확인해보고 비교해보세요!

*별이 붙은 문장이 저의 생각이고,나머지는 문제를 인용했습니다.  

* 문제를 본 나의 생각

입력 :  자연수 N (1 ≤ N ≤ 1,000,000)  ->  int타입으로 받자. 

 

1. 주어진 n 보다 작은 모든 자릿수를 더해서 n과 같으면 된다. 

*n보다 작은수들 한 번 씩 해봐도 최대 1,000,000번 연산 정도?? -> 브루트포스(완전탐색) 사용해도 된다. 

쉽게, 반복문을 0부터 입력받은 수까지 일일히 다 확인해도된다. 

 

*+추가로 한 생각 

1) 굳이 다 돌 필요 없고, 가능한 수의 최저점이 분명 있을거다.   

2) 그 bottom-Up느낌으로 밑에서부터 찾아서 올라가다가 찾으면 답을 출력하고

3) 결국 못찾아서 N과 같게된다면, 못 찾았다는 의미이니 0을 출력하자. 

 

*1)최저점이 어딜까?

테스트케이스로 주어진 216을 이용해 확인해보자.

규칙을 적용이 가능한 숫자는 198 과 207  이 2가지 경우가 있다. 

 

주어진 입력 N과 달리  / 가능한 케이스 198,207을 변수 M이라고 하자.  

다음과 같이 규칙을 정리할 수 있다. 

N =  숫자 M + M의 첫째자리 + M의 둘째자리  + M의 셋째자리 

216 = 198 + 1 + 9 + 8 

216 = 207 + 2 + 0 + 7 

 

밑줄 친 자리 수들을 유의해서 보자. 

step1 . 세자리 숫자M이라서 세 자리의 숫자를 더해야한다. 그럼 두자리 숫자M이라면 두 자리의 숫자를 더해야겠네?

step2 . 한 자리는  0~9 까지니까 최대숫자가 9이다.  즉, 198 - 9*3자리 부터 시작하면 된다.

-> 주어진 자연수 N -  M의 자리수 * 9 가 제한선이 되겠다.

 

코드를 살펴보자. 

숫자의 자릿수를 살펴보는 두 가지 방법을 나눠서 코드를 분리하였다. 

방법 1 )  문자열로 받지 않고 애초에 숫자로 입력을 받았내었다.그래서 checCnt 함수를 만들어, 일일히 자릿수를 count했다.

방법 2 )  애초에 문자열로 입력 받았고, 문자열.length()를 이용하여 문자열의 길이를 구하고, 그 다음에 int로 파싱을 했다.

방법 1

 

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

public class BOJ_2231_clear {

	public static void main(String[] args) throws NumberFormatException, 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 = checkCnt(n); 	//숫자길이 : 216이면 3 		
		
		int sum =0;				
		int number=0;
		
		for(int i= n-9*cnt;i<n;i++) {
			sum = i;
			number =i; 				//while문 내에서 돌릴 number;
			while(number!=0) {
				sum += number%10;
				number =number/10;
			}			
			if(sum==n) {
				bw.write(i+"");
				bw.flush();
				bw.close();
				br.close();
				
				return;
			}
		}
		bw.write(0+"");
		bw.flush();
		bw.close();
		br.close();
				
		
	}
	public static int checkCnt(int number) {
		int cnt=0;
		while(number!=0) {
			number = number/10;
			cnt++;
		}
		return cnt;
	}
	
}

방법 2

package bruteforce;

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

public class BOJ_2231_clear {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String strN = br.readLine();
		int cnt = strN.length();
		int n = Integer.parseInt(strN);

		
		
		int sum =0;				//합계 
		int number=0;
		
		for(int i= n-9*cnt;i<n;i++) {
			sum = i;
			number =i; 		//while문 내에서 돌릴 number;
			while(number!=0) {
				sum += number%10;
				number =number/10;
			}			
			if(sum==n) {
				bw.write(i+"");
				bw.flush();
				bw.close();
				br.close();
				
				return;
			}
		}
		bw.write(0+"");
		bw.flush();
		bw.close();
		br.close();
				
		
	}
}

 

부족하지만, 읽어주셔서 감사합니다.
혹시 보고 자유로운 코멘트나 생각이 떠올랐다면 바로바로 적어서 아이디어를 공유해주세요!!
수정할 사항이 있으면 수정하겠습니다!