[BOJ] 16676. 근우의 다이어리 꾸미기(Greedy, 탐욕 기초).py

#. Problem

https://www.acmicpc.net/problem/16676

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

0~10까지는 스티커 팩 하나로 모든 수를 하나씩 표현할 수 있다. (<11)

11~110 까지는 스티커 팩 두 개로 모든 수를 표현할 수 있다. (<111)

111~1111 까지는 스티커 팩 세 개로 모든 수를 표현할 수 있다. (<1111)

그리디 문제는

1. 최적의 상태가 존재하는가

2. 어떤 규칙성이 존재하는가

3. 이 선택을 했을 때, 다음 선택에 최적화 or 규칙이 똑같이 적용되는가

를 확인해주어야 한다.

#. Python Code

N = input()
S = '1' * len(N)
 
if len(N) == 1:
    print(1)
elif int(N) >= int(S):
    print(len(N))
else:
    print(len(N)-1)

ex) N = 88

line 2) 입력받은 정수의 길이를 '1'로 표시

line 4) N이 일의 자리 정수라면 1 출력

line 6) N이 11보다 크거나 같다면 두 개의 스티커 팩으로 표현 가능

line 8) N이 11보다 작다면(10인 경우) 한 개의 스티커 팩으로 표현 가능

#. Other Code

n=int(input())
i,j=11,1
 
while n>=i:
 i=i*10+1
 j+=1
 
print(j)

더더더 간결해진 코드다. 조건문도 줄어서 더 빠르다.

line 2) i를 기준 11로 정하고, j는 자릿수를 저장

line 4) n이 i보다 크거나 같을 때까지 반복

line 5) n이 i보다 크거나 같다면, '11'은 '111'로, '111'은 '1111'로

line 6) 자릿수를 늘려준다.