1065번 한수 문제
백준 완전탐색 문제
문제 링크
본 문제는 C++17을 이용하여 해결하였다.
처음 풀어본 완전탐색 알고리즘 문제이다. 문제를 보자.
문제
어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.
시간 제한 메모리 제한 2초 128MB
입출력 예
INPUT OUTPUT 110 99 1 1 210 105 1000 144
문제 해결
문제 해석
해석을 해보면 입력받은 N 이하의 자연수들 중 문제에서 정의한 한수의 개수를 세라는 것이다.
여기서 주의해야될 것은 100 미만의 1자리 자연수 혹은 2자리 자연수이다. 이 수들은 자리수가 2자리 이하기 때문에 무조건 등차수열을 이룬다.
예를 들어 98은 -1 을 등차로 가진 등차수열이라는 뜻이다.
코드
처음으로 풀어본 완전탐색 알고리즘 문제였다. 또한 알고리즘 문제를 C++로 풀어본 것도 처음이다.
내가 쓴 코드를 보자.
int N, ret=0;
vector<int> val;
void splitNum(int n){
while(n!=0) {
val.push_back(n%10);
n/=10;
}
}
int solve(int N) {
if(N<100) return N; //기저사례 : 입력받은 수가 100 미만
if(N == 1000) ret -= 1; // 기저사례 : 입력받은 수가 1000
for(int i=100; i<=N; ++i) {
splitNum(i);
if((val[2] - val[1]) == (val[1]-val[0]))
ret += 1;
val.clear();
}
return ret+99;
}
int main() {
cin >> N;
cout << solve(N) << endl;
}
Hansu Problem
solve 함수를 보면 N 이 100 보다 작으면 N 그 자체를 return 하는 것을 볼 수 있다. 또한 1000일 경우 리턴값을 -1을 하는 것을 볼 수 있다. 그 이유는 solve 함수 중간에 if((val[2] - val[1]) == (val[1]-val[0])) 에서 잠정적으로 입력받은 수가 3자리 수라고 가정했기 때문이다. 만약 1000이 입력되면 (val[2] - val[1]) == (val[1]-val[0]) 이 항상 참이 되기 때문에 따로 처리한다.
splitNum 함수는 입력받은 숫자를 각 자리수로 나누는 역할을 한다. 자리수별로 나눈 숫자들은 val 벡터에 넣게된다.
마무리하며
완전탐색 문제 중에서 쉬운 편에 속한 문제이다. 하지만 C++ 을 많이 안써서 그런지 로직을 짜고 코드를 적는데 오랜 시간 걸렸다. 알고리즘 테스트 문제들을 통해서 점점 익숙해져야겠다.
