[JAVA] 2231번 분해합 (브루트포스 알고리즘)

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

2231번: 분해합

 

🌌 전체 코드 (밑에 응용 버전O)

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

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

		int cnt=0;
		
		for(int i=0; i<N; i++) {
			int num=i;
			int sum=0;
			
			while(num != 0) {
				sum+=num%10;	//1자리 수부터 계산하여 sum에 합계
				num/=10;		//앞자리 수 숫자 계산을 위해 10 나누기
			}
			
			if(sum+i==N) {
				System.out.println(i);
				cnt++;
				break;
			} 
		}
		
		if(cnt==0) {
			System.out.println(0);	//생성자가 없으면 0 출력
		}
	}
}

---

브루트포스 알고리즘은 0부터 목표 수까지 그냥 돌리면 돼서 쉬운데 코드를 짤 때 완전탐색 방식으로 짜지 않다보니 꼬이고 꼬이는 편이다.. 풀이를 보면 쉬운데 보기 전에는 혼자 우주까지 가버린다. 여러 문제를 풀면 쉽게 풀릴거 같으니 문제를 많이 풀어봐야겠다.

 

완탐 방식을 생각못하고 효율적으로 짜야겠다며 처음엔 236이 주어지면 2이하, 3이하, 6이하의 숫자만 올 수 있어서 이를 코드로 녹이려고 했는데 중첩의 중첩 반복문이 될 아이디어였다.

 

해당 코드는 나의 가상스승님이신 블로거님 코드를 참고하였다.

https://st-lab.tistory.com/98

[백준] 2231번 : 분해합 - JAVA [자바]

---

for(int i=0; i<N; i++) {
    int num=i;
    int sum=0;

    while(num != 0) {
        sum+=num%10;	//1자리 수부터 계산하여 sum에 합계
        num/=10;		//앞자리 수 숫자 계산을 위해 10 나누기
    }

    if(sum+i==N) {
        System.out.println(i);
        cnt++;
        break;
    } 
}

 

백준 예제로 실행해본다고 가정

while(num!=0){
    sum+=num%10;
    num/=10;
}

> num = 198 일 때,

 

1) sum = 8; num = 19;

sum+=198%10;

num/=10;

 

2) sum = 17; num = 1;

sum+=19%10;

num/=10;

 

2) sum = 18; num = 0;

sum+=1%10;

num/=10;

 

if(sum+i==N) {
    System.out.println(i);
    cnt++;
    break;
}

18+198 = 256;

생성자가 없을 경우를 생각해서 카운팅하고

제일 작은 수의 생성자를 출력해야하기 때문에 break문으로 for문을 탈출

 

---

🌌 전체 코드

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

public class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String strN = br.readLine();
		int str_len = strN.length();	//N의 자릿수
		int N = Integer.parseInt(strN);	//int로 형타입 변환
		int cnt=0;
		
		for(int i=N-(str_len*9); i<N; i++) {
			int num=i;
			int sum=0;
			
			while(num != 0) {
				sum+=num%10;	//1자리 수부터 계산하여 sum에 합계
				num/=10;		//앞자리 수 숫자 계산을 위해 10 나누기
			}
			
			if(sum+i==N) {
				System.out.println(i);
				cnt++;
				break;
			} 
		}
		
		if(cnt==0) {
			System.out.println(0);
		}
	}
}

---

처음엔 이게 무슨 소리지 했다. 근데 겁나 간단함.

 

예를들어, 1234와 같은 4자리 수가 N으로 주어진다면

자릿수 별 합은 9+9+9+9가 최대가 되기 때문에 최댓값 9와 자릿수를 곱해야한다.

이를 N에서 빼면 최소 N-(str_len*9)부터 N까지의 숫자만 생성자가 될 수 있다.

 

생성자가 될 수 있는 최솟값은 1234-(9*4)인 것.

1234의 생성자 x를 구할 때

36+x = 1234니깐! x=1234-36!! 

for(int i=N-(str_len*9); i<N; i++) {
	...
 }