[백준 / 1526] 가장 큰 금민수 - Python

http://acmicpc.net/problem/1526

1526번: 가장 큰 금민수

 

<풀이>

금민수는 7과 4로 이루어진 가장 큰 수이다. 따라서 입력받은 수와 같은 자릿수의 7로 이루어진 수가 가장 큰 수 일 것이다. 해당 수부터 차례로 4로 바꾸면서 입력받은 수보다 처음으로 작아지는 수가 제일 큰 수 일 것이다.

 

예를 들어 4자리의 수가 입력이 되면 7777부터 7774, 7747, 7744, 7477... 순서로 점점 작아지면서 입력 수보다 작은 처음 수를 탐색을 한다.

n자릿수가 입력이 되면 총 2^n번 반복이 된다. 위의 경우 4자리 수이므로 총 16개의 은민수가 만들어진다. 그리고 각 자리의 4와 7의 반복을 보면 처음 자리는 2^3번마다 수가 바뀌고, 백의 자리는 2^2마다, 십의 자리는 2^1마다, 일의 자리는 2^0마다 수가 바뀌는 것을 볼 수 있다. 즉 천의 자릿수는 8번째 은민수부터 4로 바뀌므로 8//(2^3)의 몫이 홀수인 경우부터 수가 바뀐다. 백의 자리는 4에서 바뀌고, 8에서 다시 바뀌고, 12에서 다시 바뀌므로 n//(2^2)의 몫이 홀수인 경우 4, 짝수인 경우 7인 것을 알 수 있다. 따라서 해당 규칙을 일반화하면

for i in range(자릿수):
	if (n // (2**j)) % 2 == 0:
    	은민수에 7을 추가
    else:
    	은민수에 4를 추가

 

만약 4444 미만의 수는 금민수가 4자릿수가 아닌 777인 세자리 수이므로 해당 과정을 통해서 찾지 못하면 한 자리수 작은 7로 이루어진 은민수가 제일 큰 금민수이다.

<입력 및 연산>

N = input()

find = False

for i in range(2**len(N)):
    answer = ''
    for j in range(len(N)):
        if (i//(2**j)) % 2 == 0:
            answer = '7'+answer
        else:
            answer = '4'+answer

    if int(answer) <= int(N):
        find = True
        break

 

수를 입력받는다.

 

find는 위의 과정으로 수를 찾지 못하는 경우 한 자리수 작은 7로 이루어진 수가 금민수 임을 알아내기 위한 변수이다.

 

n자리의 은민수를 만드는 경우는 2^n의 경우이므로 해당만큼 반복해준다. 해당 자릿수의 은민수는 answer에 저장해주기 위해 선언한다.

 

맨 뒤의 일의 자리부터 은민수를 만들어 준다. 위에서 본 것처럼 일의 자리는 2^0마다 수가 바뀌고, 십의 자리는 2^1, 백의 자리는 2^2 등등 자리가 바뀌므로 2^n으로 나눠준 몫이 짝수이면 7이고, 홀수이면 4이다.

 

만들어진 은민수가 만약 N보다 처음으로 작아지게 된다면 해당 수가 금민수이고, 해당 조건문을 종료하고 find를 True로 바꿔준다.

<출력>

if not find:
    answer = ''
    for i in range(len(N)-1):
        answer += '7'

print(answer)

 

만약 위의 경우에서 금민수를 찾지 못한 경우 한자리 작은 7로 이뤄진 은민수가 금민수이므로 해당 수를 answer에 넣어준다.

<전체 코드>

N = input()

find = False

for i in range(2**len(N)):
    answer = ''
    for j in range(len(N)):
        if (i//(2**j)) % 2 == 0:
            answer += '7'+answer
        else:
            answer += '4'+answer

    if int(answer) <= int(N):
        find = True
        break

if not find:
    answer = ''
    for i in range(len(N)-1):
        answer += '7'

print(answer)