SWEA 1288 [D2] (C++) 새로운 불면증 치료법

우리누리·2022년 8월 8일
0

SWEA

목록 보기
2/8

출처
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN&categoryId=AV18_yw6I9MCFAZN&categoryType=CODE&problemTitle=1288&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

문제

민석이는 불면증에 걸렸다. 그래서 잠이 안 올 때의 민간요법 중 하나인 양 세기를 하려고 한다.

민석이는 1번 양부터 순서대로 세는 것이 재미없을 것 같아서 N의 배수 번호인 양을 세기로 하였다.

즉, 첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다.

이렇게 숫자를 세던 민석이에게 잠은 더 오지 않고 다음과 같은 궁금증이 생겼다.

이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 최소 몇 번 양을 센 시점일까?

예를 들어 N = 1295이라고 하자.

첫 번째로 N = 1295번 양을 센다. 현재 본 숫자는 1, 2, 5, 9이다.

두 번째로 2N = 2590번 양을 센다. 현재 본 숫자는 0, 2, 5, 9이다.

현재까지 본 숫자는 0, 1, 2, 5, 9이다.

세 번째로 3N = 3885번 양을 센다. 현재 본 숫자는 3, 5, 8이다.

현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다.

네 번째로 4N = 5180번 양을 센다. 현재 본 숫자는 0, 1, 5, 8이다.

현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다.

다섯 번째로 5N = 6475번 양을 센다. 현재 본 숫자는 4, 5, 6, 7이다.

현재까지 본 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9이다.

5N번 양을 세면 0에서 9까지 모든 숫자를 보게 되므로 민석이는 양 세기를 멈춘다.

[입력]

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.

이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.

각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 정수 N, M이 주어진다. (1 ≤ N ≤ 30 , 0 ≤ M ≤ 108)

[출력]

각 테스트 케이스마다 한 줄씩

마지막 N개의 비트가 모두 켜져 있다면 ON

아니면 OFF 를 출력하라.

코드

#include <iostream>
using namespace std;


int main()
{
	int test_case,n,s_n,mul,flag=0;
	cin >> test_case;
	for (int i = 0; i < test_case; i++)
	{
		cin >> n;
		mul = 0;
		while (1)
		{
			mul += n;
			s_n = mul;
			while (s_n > 0)
			{
				flag |= (1 << s_n % 10);
				s_n = s_n / 10;
			}
			if (flag == (1 << 10) - 1)
			{
				cout << "#" << i + 1 << " " << mul << endl;
				flag = 0;
				break;
			}
		}
	}
	return 0;
}

설명

비트연산을 이용하여 간단하게 구현할 수 있었다.

mul 변수에 반복문 횟수만큼의 N을 저장한다. 즉 X번 째의 N의 값을 저장
s_n에 mul을 복사하여 N, 2N, 3N ..... XN의 값을 저장한다.

s_n의 일의 자리 수부터 구하여 값을 flag에 누적시킨다.
그리고 s_n을 10으로 나눈 몫을 저장하여 자리수를 하나씩 내려준다. ex) 123 -> 12

이 과정을 반복하여 flag에 s_n의 각 자릿수들을 누적시켜 저장하는데
0~9까지의 자릿수가 모두 누적이 된다면 flag는 0~9까지의 비트 값이 모두 1로 된다.
비트 연산에 의하면 2^(n) - 1 = 2^(n-1) + 2^(n-2) + ...... 2^(0) 이므로
flag == (2^10 - 1) 인 경우 문제의 조건을 만족한다.

후기

비트연산을 이용하면 매우 간단하게 풀 수 있는 문제들이 종종 보인다.
<< >> 시프트 연산과 |= &=로 교집합 합집합 개념을 잘 이해하고 넘어가야겠다.

(문제 다 포스팅하려면 시간이 좀 걸릴거 같다...)

0개의 댓글