[ALPS Study] 완전탐색 - 블랙잭2, 영화감독 숌

오늘 풀 문제는 총 세 문제였지만 생각보다 프로젝트 회의가 늦게 끝나서 우선 벌점은 면하기 위해.. 두 번째 문제인 영화감독 숌 문제만 먼저 풀어서 올려 놓아야겠다...  12시 이후에 나머지 문제도 풀어볼 예정이다. (굉장히 정신이 없다)

 

- BOJ 2798 블랙잭(2) 

 

 

 

- BOJ 1436 영화감독 숌

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int ok(int num);
int main() {
	int N,cnt=0,i;
	scanf("%d", &N);
	for (i = 666; cnt != N; i++) {
		if (ok(i))
			cnt++;
	}
	printf("%d", --i);
}
int ok(int num) {
	int tmp = num;
	int a;
	int cnt = 0;
	while (tmp) {
		a = tmp%10;
		if (a == 6)
			cnt++;
		else
			cnt = 0;
		if (cnt >= 3)
			return 1;
		tmp /= 10;
	}
	return 0;
}

 한 번에 맞아서 굉장히 신이 난다!!! 사실 잘 짠 코드인지는 모르겠다. 시간이 없ㄷ.. 일단 내고 고치던가 해야지..ㅎ 사실 이 문제도 보자마자 이 생각을 했다. "설마 이거 다 대입해봐야해?" main 함수 안에서 다 짜려고 했더니 너무 지저분해져서 힌트를 얻고자 스터디 영상을 봤는데 함수로 빼서 구현해야겠다는 힌트를 얻을 수 있었다!

 

- 기본적인 원리

 

원리는 간단하다.

1. 모든 정수를 검사한다.

2. 조건에 맞는(6이 연속 3번 나오는) 정수일 경우 cnt을 증가시킨다.

3. cnt와 N이 같아지는 순간의 정수가 바로 N번째 종말의 수이므로 이 때의 수를 출력한다.

 

main에서는 모든 정수를 돌려보는 역할을 한다. 어차피 첫 번째 종말의 수는 666부터 시작이므로 굳이 1부터 시작하지 않고 666 부터 시작했다. cnt와 N이 같지 않을 동안 for문을 반복해주며 i를 증가시킨다. 

그러다가 N번째 종말의 수를 찾으면 for문을 탈출한다. 이 때, for문에서 나오기 직전에 i++이 되므로, print하기 전에 --i를 해준다. 

 

ok함수에서는 이 수가 종말의 수인지 확인하는 역할을 한다. n의 자리 수를 한 글자 한 글자 파악하기 위해 나누기 연산자와 모듈러 연산자를 사용했다.

tmp를 10으로 나눈 나머지는 1의 자리가 된다. tmp를 10으로 나누어 준 뒤 다시 while문 안으로 들어와 다시 tmp를 10으로  나눈 나머지는 10의 자리 숫자가 된다. (109%10 = 9, 109/10 = 10, 10%10 = 0) 이런 식으로 tmp를 10으로 계속 나누어 마지막 자리까지 파악한다. 이 때, 어떤 자리 수가 6이라면 cnt를 1 증가시킨다. 다음 자리 수도 6이라면 cnt가 또 증가해 2가 된다. 만약 중간에 다른 숫자가 있다면 cnt는 0으로 초기화 된다. 연속되는 3자리가 6이어야하므로 cnt가 3이 될 때 return 1을 해주게 된다. 그렇지 않으면(모든 자리수를 검사하는 동안 계속 cnt가 2 이하라면) 연속되는 3자리 수가 6인 경우가 아니므로 return 0 을 해주게 된다. 

 

- 덧붙이기

 

사실 정말 간단한 문제였다. 각 자리수를 파악할 때 %와 / 연산자를 활용하면 된다는 사실만 알면 쉽게 풀 수 있다. 다만 나처럼, 설마 이걸 모든 정수를 검사해보라고..? 라는 생각에 코딩을 시작하지 못하고 있을 수는 있다... 더 효율적인 방법이 있을지는 고민해봐야 겠다. 사실 저 자리수 쪼개기 스킬은 이번 컴프 시험공부하면서 봤던 회문 검사 알고리즘 때문에 기억하고 있는 건데 나름 유용하다.