1065_한 수

네이버 블로그에서 써놨던 글 옮겨와 버리기!

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

1065번: 한수

1065번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 한수 풀이 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 13331 5995 5300 46.187% 문제 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.  입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이

www.acmicpc.net

이제 부터 하루에 한문제씩 내가 풀었던 문제들을 설명을 덧붙여 올리려고한다.
문제를 다시 풀면서 나에게도 도움이 될 것이도 쌓아놓으면 나중에 쓰임새도 있을 것 같고 그리고..

알고리즘 공부를 하면서 나 스스로도 찾아볼만한 마땅한 자료가 없어서 힘들었다

비록 내 코드가 다른 분들에 비해 잘짜여진 코드도 아니지만 공부하시는 분들이 (이문제에 어려움을 겪고있는 분들이) 내 코드를 보고 아 이런 아이디어도 있구나! 할 수있었으면 좋겠다
그리고 내 코드를 보고 비판 해주실 분도 있으시면 더욱 좋을 것 같다

우선, 한수 문제는 등차수열을 이루는 수의 개수를 구하는 문제이다
N으로 자연수가 주어지고 우리는 N보다 작거나 같은 한수의 개수를 출력하면 된다.

이문제를 처음 풀 때에 궁금했던 것이 1 2 3 ... 9는 한수인가? 였는데 한수이다! 예제를 풀어보면 바로알 수 있다.

1) 1부터 99까지는 모든 수가 한수이기 때문에 우선 N이 99보다 작은 수가 들어오면 그냥 그대로 N을 출력해주었다.

2) 자, 그럼 99보다 큰, 즉 3자리 이상의 수가 들어오면?
100부터 한 개씩 n까지 돌면서 검사를 해주어야한다. cnt 라는 count용 변수를 사용한다. 
0으로 설정해 놓은 다음 한 수가 나올 때 마다 더해주는것이 일차적인 개념이다.

자 그러면 그 한수는 어떻게 구할 수 있을까? 

등차수열의 첫째 개념은 "공차"이다. (공차먹고싶다...ㅈㅅ...)
공차는 쉽게 0번째 수 와 1번째 수의 차이를 구하면되는데, 문제는 우리가 받은 입력이 int형이라는 것이다. 
 int형 변수로는 각 자리수에 쉽게 접근할 수 없기 때문에 string으로 전환해주는 과정이 필요하고 이를 도와주는 함수가 to_string함수이다. string.h 라이브러리에 존재하는 함수이다.

이것을 이용해서 공차를 구한 후 부터는 뒤로 쭉쭉 나아가며 앞뒤 수의 차이가 공차와 일치하는지를 판단하면 된다.
만약 공차와 일치하지 않는 시점이 나온다면 flag를 false로 설정해주면 된다. 

포문을 나온 후 아직 flag가 true라면 공차가 틀린 적이 없는 것이므로 한수이다!
그렇다면 cnt에 값을 더해주면 된다. 

시간복잡도는 O(n)으로 해결된다. 
중간에 이중포문이 나오지만, 그래봤자 수의 자릿수만큼 돌아가는 것이기 때문에 N의 최대값이 들어와도 그리 큰 영향이 없다. 

자세한 코드는 아래에...

/* 1065번_한수 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. */ #include <iostream> #include <string> using namespace std; int n; int cnt;//결과를 담을 변수 int main() { scanf("%d", &n); if (n <= 99) { printf("%d",n); } // 99이하이면 모두 한수이므로 99출력. else//그렇지 않을 경우 { for (int i = 100; i <= n; i++) { bool flag = true; string temp = to_string(i);//int를 string으로 바꿔주기 int differ = temp[1] - temp[0]; //공차를 구하는 과정 int length = temp.length();//자릿수 = string의 길이 for (int k = 2; k < length; k++) { if ((temp[k] - temp[k-1]) != differ) { //cout << "34"; flag = false; }//공차와 다르다면 false로 설정 }//뒤에가 모두 공차와 일치하는지 판단. if (flag != false) cnt++;//한수가 맞다면 갯수에 더해주기 } printf("%d", cnt + 99); } }