[백준 알고리즘] 1065: 한수 풀이(자바)

문제

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

1065번: 한수

 

코드

import java.util.Scanner;

//등차수열: an = a1 + (n - 1)d

class Test {
	int num = 0;
	int gap = 0;
	int cnt = 0;	//한수의 갯수 카운트
	
	void hanSoo(int n) {
		if(n < 100) {	//n이 1~99일 때는 무조건 카운트 1씩 증가
			for(int i = 0; i < n; i++)
				cnt++;
		} else {	//ex.n = 203
			cnt = 99;	//기본으로 99개 깔고 시작
			
			for(int i = 100; i <= n; i++) {
				int one = i / 100;	//3 
				int hund = (i % 100) / 10;	//0
				int thou = (i % 100) % 10;	//2
				
				if(hund - one == thou - hund)
					cnt++;
			}
		} 
		System.out.println(cnt);
	}
}

public class Main {
	public static void main(String[] args) {
		Test test = new Test();	//객체 생성
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		test.hanSoo(n);
		
		sc.close();
		
	}
}

 

코드 설명

if(n < 100) {
	for(int i = 0; i < n; i++)
		cnt++;
}

 1 ~ 99까지는 무조건 한수이므로 무조건 카운트한다. 

100부터 등차수열 조건을 매겨 한수의 개수를 카운팅하면 된다. 

else {
	cnt = 99;	//기본으로 99개 깔고 시작
}

 

이제 else에 들어갈 한수 카운팅 공식 구하기.

for(int i = 100; i <= n; i++) {
	int one = i / 100;	//3 
	int hund = (i % 100) / 10;	//0
	int thou = (i % 100) % 10;	//2
}

다음 공식을 거쳐 일의 자리, 백의 자리, 천의 자리 정수를 분리한다. 

만약 n이 203이라면, one = 3, hund = 0, thou = 2가 저장된다.

 

 

등차수열 공식

an  = a1 + (n - 1)d

 

등차수열 공식에 의해,

1번째 항과 2번째 항은 d만큼 차이가 나야 하고,

3번째 항과 4번째 항 역시 d만큼 차이가 나야 한다.  

 

이제 1000의 자리수 = 1번째 항, 100의 자리수 = 2번째 항, 100의 자리수 = 3번째 항, 1의 자리수 = 4번째 항 으로 보고, 이를 이용해 100부터 i의 수를 하나씩 증가시켜 가며 한수를 구한다. 

if(hund - one == thou - hund)
	cnt++;

 

 

마무리

등차수열의 기본 원리를 파악하고 있어야 풀 수 있었던 문제.

0과 첫번째 항의 차이까지 고려해 가며 문제를 풀다 시간 낭비를 많이 했다. 

추가로 1 ~ 99까지는 무조건 한수인데 10부터 한수를 찾겠다고 해보다가 또 시간 낭비...

문제 풀기 전에 주어진 조건을 꼼꼼히 확인하고 기본 공식이나 원리 등은 알고 문제를 풀어야겠다.