[백준] C | 1065 | 한수

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

1065번: 한수

 

맨 처음 종이에 1부터 쭉 써보니까 99 전까지는 한 자릿수 또는 두 자릿수여서 한수 범위에 모두 포함되는 것을 알았다.

그래서 세자리 수를 처음부터 써보면서 차례대로 빼 보았다. 그러기를 반복하다가 문제가 풀리지 않는 답답함을 느껴 결국 해결 방법을 찾아보고 말았다.

알고리즘 공부를 시작한지 얼마 안 돼서 이런 식으로 접근하고 알고리즘 문제의 대략적인 흐름을 파악한 뒤 며칠이 걸리더라도 보지 않고 스스로 해결하는 능력을 꾸준히 키워야겠다.

 

코드 풀이

 

#include <stdio.h>

void han_soo(int N)
{
	if (N < 100)
		printf("%d", N);
	else
	{
		int cnt;
		int A, B, C; //각 100, 10, 1의 자리 표현
		cnt = 99;

		for (int i = 100; i <= N; i++)
		{
			A = i / 100;
			B = i % 100 / 10;
			C = i % 10;

			if ((C - B) == (B - A))
				cnt++;
		}
		printf("%d", cnt);
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	han_soo(N);
}

 

추가 설명 )

이 문제를 풀기 위해서는 각 자리 숫자를 추출 할 수 있는 알고리즘도 필요하다

각 자리수 추출하는 알고리즘은 많은 문제에 쓰이는데 방법을 기억해두면 좋을 거 같아서 정리해본다

1000자리 숫자의 각 자리 숫자를 구하려면 1000자리 수는 1000으로 나눈 몫이 된다

그렇다면 100의 자리 숫자는 어떻게 구할까?

1000으로 나눈 뒤 나온 나머지는 세자리 숫자가 된다

그 숫자에서 100을 나누게 되면 몫이 100의 자리 수가 되는 것이다

나머지 자리 숫자도 같은 방법으로 적용시키면 각 자릿수를 구할 수 있다

각 자리 수를 구한 뒤 한수는 각 자리 숫자가 등차수열이므로 ABC라고 하면 C-B와 B-A를 비교해주면 된다