문제 개요
매우 큰 수가 하나 주어졌을 때, 이 수를 회전(순환 이동)했을 때 나오는 값들 중 8로 나누어 떨어지는 경우가 몇 개인지 세는 것이 목표입니다.
모든 회전 값을 일일이 만들어 나눗셈을 반복하는 것은 비효율적입니다. 대신 8의 배수 판정 법칙을 활용하면 됩니다. 어떤 수의 마지막 세 자리가 8로 나누어 떨어지면 그 수 전체도 8로 나누어 떨어집니다. 예를 들어 1800의 회전 결과는 1800, 0180, 0018, 8001이며, 이 중 1800만 8로 나누어 떨어집니다.
예시로 이해하기
입력: num = 15320
출력: 8로 나누어 떨어지는 회전 수: 1
설명: 회전 결과는 다음과 같습니다.
15320, 01532, 20153, 32015, 53201 이 중 15320만 8로 나누어 떨어집니다.
입력: num = 848484
출력: 8로 나누어 떨어지는 회전 수: 3
설명: 회전 결과는 다음과 같습니다.
848484, 484848, 848484, 484848, 848484, 484848 이 중 484848은 모두 8로 나누어 떨어지므로 총 3개입니다.
알고리즘 접근 방식
수를 문자열로 변환한 뒤 for 반복문으로 탐색합니다. 연속된 세 자리씩 정수로 바꾸어 8로 나누어 떨어지는지 검사하고, 나누어 떨어질 때마다 카운트를 증가시킵니다.
수를 long long형 변수 num으로 받습니다.
함수 Rotation_8(long long num)은 num을 인자로 받아 8로 나누어 떨어지는 회전의 개수를 반환합니다.
num을 문자열로 변환합니다: str = to_string(num)
num의 자릿수는 length = str.length()로 구합니다.
세 자리 값을 저장할 임시 변수 digit = 0을 선언합니다.
초기 count는 0으로 설정합니다.
length가 1이면 한 자리 수입니다. digit = (str.at(0) - '0')으로 정수로 변환해 8로 나누어 떨어지는지 검사한 후 결과를 1 또는 0으로 반환합니다.
length가 2이면 두 자리 수입니다. part_1 = (str[0] - '0') * 10 + (str[1] - '0'), part_2 = (str[1] - '0') * 10 + (str[0] - '0')으로 두 가지 회전을 만들어 각각 검사한 후 결과를 반환합니다.
자릿수가 3 이상이면 i = 0부터 i = length-1까지 반복하며 digit = (str[i] - '0') * 100 + (str[i + 1] - '0') * 10 + (str[i + 2] - '0')으로 세 문자를 정수로 변환합니다. digit이 8로 나누어 떨어지면 count를 증가시킵니다.
마지막 자리와 처음 두 자리로 이루어진 조합에 대해서도 digit = (str[length - 1] - '0') * 100 + (str[0] - '0') * 10 + (str[1] - '0')으로 동일한 과정을 수행합니다.
8로 나누어 떨어지는지 검사하여 count를 갱신합니다.
최종적으로 count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int Rotation_8(long long num){
string str = to_string(num);
int length = str.length();
int digit = 0, count = 0;
if (length == 1){
if(digit % 8 == 0){
return 1;
}
else{
return 0;
}
}
else if(length == 2){
int part_1 = (str[0] - '0') * 10 + (str[1] - '0');
int part_2 = (str[1] - '0') * 10 + (str[0] - '0');
if (part_1 % 8 == 0){
count++;
}
if (part_2 % 8 == 0){
count++;
}
return count;
}
else{
for(int i = 0; i < (length - 2); i++){
digit = (str[i] - '0') * 100 + (str[i + 1] - '0') * 10 + (str[i + 2] - '0');
if (digit % 8 == 0){
count++;
}
}
}
digit = (str[length - 1] - '0') * 100 + (str[0] - '0') * 10 + (str[1] - '0');
if(digit % 8 == 0){
count++;
}
digit = (str[length - 2] - '0') * 100 + (str[length - 1] - '0') * 10 + (str[0] - '0');
if(digit%8 == 0){
count++;
}
return count;
}
int main(){
long long num = 24040;
cout<<"Count of rotations divisible by 8 are: "<<Rotation_8(num);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of rotations divisible by 8 are: 3