[백준 BOJ] 1065번 한수 (C++/cpp)

문제 설명

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

1065번: 한수

 

접근 방법 - 브루트포스 알고리즘에 대한 응용문제

백준의 1065번 문제는 브루트포스 알고리즘을 활용하여 해결해야 하는 연산 문제이다.

해당 문제는, 1부터 입력값(n)까지의 범위 내에서 문제에서 정의하는 "한수"의 개수를 출력해야 하는 문제이다.

여기서 한수란 간략히, 각 자릿수를 나열하였을 때 등차수열을 이루는 숫자를 뜻한다.

필자는 여기서 아래처럼 생각을 하며, 이를 토대로 코드를 작성해보았다.

등차 수열이란, 각 구간의 차이가 일정한 수열을 뜻한다.
따라서, 한 자릿수와 두 자릿수는 모두 한수로 취급하며 한수 판별에 대한 연산은 세 자릿수부터 하도록 하였다.

입력값의 범위는 1000 이하이기 때문에, 사실상 한수 판별의 연산은 세 자릿수의 숫자만 하면 된다.

더 자세한 설명은 아래에 연이어서 하고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 값(n)을 입력받는다.

(여기서 n이 100 미만이라면 범위 내의 모든 숫자가 한수이다. 따라서 이 경우엔, n을 출력하고 즉시 실행 종료한다.)

 

2) 한수의 개수를 저장할 변수 cnt를 99로 초기화하여 선언한다.

(이 선언문은 n이 100 이상의 값을 가질 때 실행되며 100 미만의 숫자는 모두 한수이기 때문에, 해당 변수를 99로 초기화하도록 하였다.)

 

3) 반복문을 실행하여 100 이상의 수의 판별을 시작한다.

- 각 자릿수를 추출하여 이들 사이에서 등차 수열이 이루어진다고 판단되면, 이는 한수이다. 이러한 경우엔, cnt에 1을 추가한다.

- 해당 연산을 n 이하까지 실행하도록 한다.

 

4) n까지 모든 판별이 끝났다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1065번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	if (n < 100) {
		cout << n << endl;
		return 0;
	}

	int cnt = 99;
	for (int i = 100; i <= n; i++) {
		int n1 = i / 100;
		int n2 = i % 100 / 10;
		int n3 = i % 10;
		if (n1 - n2 == n2 - n3) { cnt++; }
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.03.27 백준 1065번 문제 제출 결과)