https://www.acmicpc.net/problem/1511
분류 : Greedy
최근 코테 흐름에 DP는 거의 나오지 않고 그리디와 구현 문제가 많이 나온다고 한다. 그래서 이번 문제는 그리디 분야로 선정했다.
1511번이라는 초기 문제임에도 불구하고 맞힌 사람이 50명도 채 되지 않는 꿀잼 문제라고 생각했다.
접근 방법
문제는 참 간단하다. 최디 50개의 숫자 카드가 있고, 인접한 숫자가 없이 가장 큰 수를 만드는 것.
예제만 봐도, 주어진 모든 숫자를 전부 사용하지 못하는 경우가 존재한다.
따라서, 가장 큰 수를 만든다는 것은 다음 두 단계를 고려하면 될 것 같다.
1단계. 자릿수를 최대한 크게 만든다.
2단계. 자릿수를 확정지은 후, 큰 수를 먼저 나열한다.(다만 같은 수가 연속되지 않도록)
1. 사용할 숫자카드 결정(자릿수를 크게 만들기)
숫자의 크기보다 중요한 것이, 최대한 많은 숫자 카드를 이용하여 숫자를 만드는 것이다.
- 모든 숫자 카드 사용 가능
- 모든 숫자 카드 사용 불가능
위의 두 경우로 나눌 수 있다.
첫 번째의 경우, 1단계에서는 더 고려할 것이 없고 2단계로 넘어간다.
두 번째의 경우, 사용할 수 없는 숫자를 전부 제거하고 2단계로 넘겨주면 된다.
모든 숫자카드를 사용 불가능한지 판별하려면 어떻게 하면 좋을까?
특정 숫자 카드를 최대한 많이 사용하는 방법은, 1개 간격으로 배치하는 것이다.
Ex) 1919191, 51525, 808080
특정 숫자카드의 개수를
n, 전체 숫자카드의 개수를length라고 하자
length가 홀수인 경우n <= (length+1)/2이면 모든 숫자 카드를 사용할 수 있다.
(해당 숫자 카드가 0인 경우,n <= (length)/2이면 모든 숫자 카드를 사용할 수 있다.)
length가 짝수인 경우n <= (length)/2이면 모든 숫자 카드를 사용할 수 있다.
판별 이후에는, 최소한의 카드를 제거하면 된다.
다행인 점은 숫자카드를 버리게 된다는 것은 해당 숫자카드가 절반을 초과한다는 뜻이다. 두 종류 이상의 숫자 카드를 버릴 필요가 없고, 가장 개수가 많은 숫자카드 한 종류만 버리면 된다.
그러므로 가장 많은 개수의 숫자카드를 파악한 뒤, 위의 조건에 맞게 개수를 변경해 준 뒤 2단계로 넘겨준다.
2. 큰 수 먼저 나열 + 연속되게 배치하지 않기
1단계에서 필요한 숫자를 전부 받았으므로, 모든 숫자를 사용하면 된다.
큰 숫자 먼저 나열하되 이전에 사용했던 숫자를 lastNum 변수로 기억하도록 하자.
그리고 중요한 것이, 숫자가 겹치면 안되므로 무조건 지금 배치해야만 하는 숫자는 우선적으로 배치를 해야 한다.
무조건 지금 배치해야만 하는 숫자란?
39393처럼 전체 길이가 홀수이고 해당 숫자카드의 개수가(length-1)/2인 숫자카드를 말한다.
cf) 03030같은 경우는 1단계에서 걸러졌으므로 고려하지 않아도 된다.
따라서 다음과 같은 프로세스로 숫자카드를 배치한다.
- 무조건 지금 배치해야만 하는 숫자 배치
- 바로 이전에 사용하지 않은 숫자이면서 가장 큰 수
풀이
# li로 가장 큰 수 만들기
def solve(li):
lastNum = -1
while sum(li)>0:
maxIdx = -1
maxCnt = -1
biggestNum = -1
for i in range(10):
if li[i] !=0 and lastNum !=i :
biggestNum = i
if li[i] >= maxCnt:
maxCnt = li[i]
maxIdx = i
# 많은 숫자를 반드시 써야하는 경우
# 13131과 같은 경우, 1을 무조건 써야함
if maxCnt/sum(li) > 0.5:
selectedNum = maxIdx
else:
selectedNum = biggestNum
print(selectedNum,end="")
li[selectedNum]-=1
lastNum =selectedNum
li = list(map(int,input().split()))
length = sum(li)
maxCnt = max(li)
isAllCard = False
# 모든 카드 사용 여부 판단
if (length+1) //2 >= maxCnt :
isAllCard = True
# 0은 맨 앞에 올 수 없으므로, 04040과 같은 경우 제외
if length%2 ==1 and (length+1) //2 == li[0] :
isAllCard = False
# 사용 못하는 숫자는 개수를 줄이기
if isAllCard == False:
# 0이 너무 많은 경우
if maxCnt == li[0]:
li[0] = max(1,sum(li[1:10]))
# 1~9가 너무 많은 경우
else :
maxIdx = li.index(maxCnt)
li[maxIdx] = sum(li)-li[maxIdx] +1
solve(li)이번 문제는 접근 방법을 떠올리기에 어렵진 않았던 것 같다.
숫자 0에 대한 예외가 상당히 귀찮을 줄 알았는데, 그럭저럭 할만 했다.
다만 반복문을 돌릴때 자잘하게 고려할 사항이 많았다. 실수하기 딱 좋은 문제라고 생각한다.
