1065번: 한수
어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.
www.acmicpc.net
등차수열 = 증가하거나 감소하는 수치가 일정한 수열
각 자리수마다 0~9의 숫자가 올 수 있으므로 i=0부터 i<10까지 반복문을 만들고
반복문 안에 재귀를 돌려 나오는 모든 경우의 수를 구한다. 재귀호출 할때마다 뽑은 숫자를 배열에 넣었을 때의 정수값(pNum)과 뽑은 숫자의 개수(pick)을 인자로 넘겨주었다. 코드를 본다면 쉽게 이해할 수 있을 것이라 생각한다.
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> picked;
int cNum;
int cArrLen = 1;
int cnt = 0;
void Solution(int pNum, int pick)
{
if (cNum < pNum) return;
if (pick > 0 && pick <= cArrLen)
{
if (pick == 1 || pick == 2) cnt++;
else
{
int comp = picked[0] - picked[1];
for (int i = 1; i < pick-1; i++)
{
if (picked[i] - picked[i + 1] != comp)
break;
cnt++;
}
}
}
for (int i = 0; i < 10; i++)
{
if (pick == 0)
if (i == 0) continue;
picked.push_back(i);
Solution((pNum * 10) + i, pick + 1);
picked.pop_back();
}
}
int main(void)
{
cin >> cNum;
int temp = cNum;
while (temp / 10 != 0)
{
temp /= 10;
cArrLen++;
}
Solution(0,0);
cout << cnt << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 12day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 12100번: 2048(Easy) (C++) (0) | 2020.04.19 |
|---|---|
| 백준 15683번: 감시 (C++) (0) | 2020.04.18 |
| 백준 15686번: 치킨 배달 (C++) (0) | 2020.04.15 |
| 백준 14500번: 테트로미노 (C++) (0) | 2020.04.15 |
| 백준 14889번: 스타트와 링크 (0) | 2020.04.14 |