[Java] SWEA 7854번 최약수

SW Expert Academy

---

풀이

최약수를 구해보면

한자리의 숫자는 1, 2, 5

두자리의 숫자는 10, 20, 25, 50

세자리이상의 숫자는 100...0, 125...0, 200...0, 250...0, 500...0 이 됩니다.

 

우선 입력받은 숫자의 자리수 이하의 최약수는 전부 포함되야하므로 작은 자리수의 최약수의 개수를 모두 더해주었습니다.

다음으로 한자리일 경우 각 자리수의 최약수를 저장한 num배열의 1행을, 두자리일 경우 2행을, 세자리 이상일 경우 3행을 이용해서 최약수보다 입력받은 수가 크거나 같으면 해당 최약수는 포함되므로 개수를 +1하여 해결했습니다.

이때, 세자리 이상일 경우 100, 125, 200, 250, 500이 항상 맨 앞 세자리는 고정되있으므로 temp변수에 입력받은 숫자의 맨 앞 세자리를 따로 뺀 숫자를 만들었습니다.

---

코드

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

public class Solution {
	public static int answer;
	public static int X;
	// 최약수를 저장
	public static int[][] num = {{1, 2, 5}, {10, 20, 25, 50}, {100, 125, 200, 250, 500}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			X = Integer.parseInt(br.readLine());
			
			// 최약수
			// 1, 2, 5
			// 10, 20, 25, 5
			// 100, 125, 200, 250, 500
			// 1000, 1250, 2000, 2500, 5000
			// ...xx100, ...xx125, ...xx200, ...xx250, ...xx500
			
			int len = Integer.toString(X).length();
			
			answer = 0;
			
			// 입력받은 숫자의 자리수보다 적은 자리수의 최약수는 모두 포함되므로
			// 다 더해주어야 한다.
			if (len > 1) {
				answer += 3;
			}
			
			if (len > 2) {
				answer += 4;
			}
			
			// 3자리 이상부터는 최약수가 5개씩만 있다
			for (int i = 3; i < len; ++i) {
				answer += 5;
			}
			
			if (len < 3) {
				for (int j = 0; j < num[len - 1].length; ++j) {
					if (num[len - 1][j] <= X) {
						answer++;
					}
					else {
						// 배열에 오름차순으로 최약수가 저장되있기에 뒤에 내용을 비교해봤자
						// 다 큰 수 이므로 할 필요가 없다.
						break;
					}
				}
			}
			else {
				int temp = Integer.parseInt(Integer.toString(X).substring(0, 3));
				
				for (int i = 0; i < 5; ++i) {
					if (num[2][i] <= temp) {
						answer++;
					}
					else {
						// 배열에 오름차순으로 최약수가 저장되있기에 뒤에 내용을 비교해봤자
						// 다 큰 수 이므로 할 필요가 없다.
						break;
					}
				}
			}
			
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
}

---

pyo7410/Algorithm