https://www.acmicpc.net/problem/2659
문제
위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다.
모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다.
입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오.
예를 들어서, 다음과 같은 십자 카드의 시계수는 1122이며, 이 시계수보다 작은 시계수들은 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119 뿐이므로 1122는 10번째로 작은 시계수다. (여기서 십자카드는 0 이 나타날 수 없으므로 1120은 시계수가 될 수 없다. 또한 1121 이 적혀있는 카드의 시계수는 1112이므로, 1121은 시계수가 될 수 없다.
입력
입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다.
출력
입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 출력한다.
< 구해야 하는 게 뭔지 파악하기 >
숫자 4개가 주어지고, 시계방향으로만 돌아갈 수 있을 때 만들어질 수 있는 최소값을 시계값이라고 한다.
그 시계값을 구했을 때, 그 시계값보다 작은 시계값이 몇개 존재하는지 구해야하는 문제이다.
구해야하는 걸 알았으니 어떻게 해야할까?
< 사용할 자료구조 판단 및 알고리즘 파악하기 >
나는 어처피 4개의 수로 만들어낼 수 있는 시계값의 경우의 수는 4개만 존재한다고 판단했고, 그 시계값을 하나하나 만들어보기 위해서 덱이라는 자료구조를 써야겠다고 생각했다. 앞에서 빼고 뒤에 붙이고, 위 과정으로 최소값을 구하자.
-> 시계값을 구하기 위해 덱이라는 자료구조를 통해 앞에서 빼고 뒤에 추가하는 과정으로 4번 반복을 통해 최소가 되는 시계값을 구헌다.
위 과정으로 시계값을 구했다면, 다음으로 알아내야하는 것은 내가 구한 시계값보다 작은 시계값이 몇 개인가?
이것이다. 이건 어떻게 구해야할까
어처피 시계값의 최초시작값은 1111이 된다. (1부터 9까지의 수만 사용)
그리고 1111부터 내가 구한 시계값까지 하나 하나 검사해주는 방법으로 할 것 같다. 어처피 4자리 수밖에 되지 않고, for문을 통해 해도 1만번이 넘지 않기에 시간복잡도 문제는 생각하지 않아도 될 것이다.
0이 존재하는 수는 배제해야하는 거 아닌가?
-> 어처피 0이 존재하는 수의 시계값을 구하려한다면 자리수가 줄어들 수 밖에 없다.
0이 앞에 오게 되는 순간 자리수가 줄어들기 떄문
그럼 for문을 통해 1111부터 내가 구한 시계값까지의 수를 x로 한다면 그 x가 될 수 있는 시계값을 구한다.
int isCircleNum(int num) {
int temp = num;
for (int i = 0; i < 3; i++) {
num = num % 1000 * 10 + num / 1000;
if (temp > num) temp = num;
}
return temp;
}
위 코드는 하나의 수의 시계값을 판단하는 것이다. 3번의 반복을 통해 시계값을 확인하는 건데 맨 처음에 함수로 전달받는 수를 저장해주고, 전달받은 수를 반복문을 통해 (앞에서 하나의 수를 빼고 뒤에 붙이는 과정) 저장한 수보다 작아지게 될 경우 저장된 수를 작아진 수로 변경하는 것이다. 그리고 마지막에 그 수를 반환하는 건데 반환값이 맨 처음 함수로 전달한 값과 다르다는 것은 내가 입력한 4개의 수로 만들 수 없는 시계값이라는 것을 의미하기 때문에 개수를 세지 않는다
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;
// BOJ :: https://www.acmicpc.net/problem/2659
int isCircleNum(int num) {
int temp = num;
for (int i = 0; i < 3; i++) {
num = num % 1000 * 10 + num / 1000;
if (temp > num) temp = num;
}
return temp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
deque<int> dq;
// 기준점을 덱에 푸쉬해서 4자리의 수를 만듬
for (int i = 1; i <= 4; i++) {
int x; cin >> x;
dq.push_back(x);
}
int minV = INF;
for (int i = 1; i <= 4; i++) {
int val = 0; int s = 3;
for (int j = 0; j < dq.size(); j++) {
int data = dq.front();
dq.pop_front();
val += (data * (int)pow(10, s));
s--;
dq.push_back(data);
}
minV = min(minV, val);
int x = dq.front();
dq.pop_front();
dq.push_back(x);
}
//cout << "Min Vale : " << minV << endl;
int Answer = 0;
for (int i = 1111; i <= minV; i++) {
if (isCircleNum(i) == i) Answer++;
}
cout << Answer << endl;
return 0;
}
'BOJ > 수학' 카테고리의 다른 글
[C/C++] 백준 - 2312번 : 수 복원하기 (0) | 2022.05.26 |
---|---|
[C/C++] 백준 - 5347번 : LCM (0) | 2021.09.20 |
[C/C++/Python] 백준 - 2004번 : 조합 0의 개수 (0) | 2021.09.02 |
[C/C++] 백준 - 2981번 : 검문 (0) | 2021.07.15 |
[C/C++] 백준 - 3036번 : 링 (0) | 2021.07.14 |