Baekjoon 백준 알고리즘 - 체인 ( 2785 )

1. 문제 소개

• 그리디 문제로 분류 된다.
• 체인의 개수와 길이로, 하나의 긴 체인을 묶기 위한 최소한의 고리 수를 찾는 문제이다.
• 체인의 길이는 고리의 개수와 같고, 체인을 분리하거나 연결할 수 있다는 내용을 이해해야 한다.

 

2.코드 ( python ) 

# 고리의 최소 개수 리턴 
def getMinimumChainRing(chains,v_chains):
    # 마지막 고리 위치
    endRingPos = chains-1
    # 시작 고리 위치
    startRingPos = 0
    while(True):
    	# 고리의 위치가 만나는 지점에서 break 
        if  startRingPos == endRingPos:
#            print("minimum chain Ring count : {} ".format(chains - 1 endRingPos))
            break
        elif v_chains[startRingPos]==0:
            startRingPos+=1
        else:
            v_chains[startRingPos]-=1
            endRingPos-=1

    return (chains - endRingPos -1)



def solution():
	# 입력값 전처리 
    chains = int(input())
    org_v_chains = input().split(" ")
    #chains = 5
    #org_v_chains=[1,1,1,2]
    #org_v_chains=[4,3,5,7,9]
    v_chains = [int(x) for x in org_v_chains]
    
    # 체인 개수와 정렬된 상태의 체인 길이 배열을 매개변수로 전달 
    minRings = getMinimumChainRing(chains,sorted(v_chains))
    
    # 정답 출력
    print(minRings)


if __name__=="__main__":
    solution()

 

3.코멘트

• 예제 입출력이 이해가 잘 안갔지만, 함께 스터디한 찬의님의 도움으로 이해할 수 있었다.
  • ex) 5 / 4,3,5,7,8.  
  • 3짜리를 하나 빼서 4,5,7,8 사이에 하나씩 연결하면, 최소 3개의 고리가 필요하게 된다.
• 아이디어
  • 체인을 정렬한다
  • 최소 길이의 체인부터 고리를 하나씩 빼서, 마지막 위치에서부터 차례로 연결한다. 
  • 시작 포인터에서 고리를 빼고, 마지막 포인터에서 고리를 연결하여 둘이 만나는 지점에서 break 후 정답을 출력한다.