[조합+구현]14889번, 15868번,18406번

1. 럭키 스트레이트

링크 - https://www.acmicpc.net/problem/18406

코드

import sys
input = sys.stdin.readline
n = input().rstrip()
mid = len(n)//2

comp=0
for i in range(mid):
    comp+=int(n[i])
comp2 = 0
for i in range(mid,len(n)):
    comp2+=int(n[i])
    
if comp==comp2:
    print("LUCKY")
else:
    print("READY")

자릿수를 기준으로 더해야 하기 때문에 문자열로 받아서 연산을 해주었다.

2. 스타트와 링크

링크 - https://www.acmicpc.net/problem/14889

코드

from itertools import combinations
import sys

input = sys.stdin.readline

n = int(input())
mid = n//2
member = [i for i in range(n)]
graph=[list(map(int,input().split())) for i in range(n)]

teams = list(combinations(member,mid))

diff=int(1e9)
for i in range(len(teams)//2):
    #start팀
    start=teams[i]
    total_1 = 0
    for j in range(mid):
        a = start[j]
        for k in range(j,mid):
            b = start[k]
            total_1 +=graph[a][b]+graph[b][a]
    #link팀
    link=teams[-1-i]
    total_2 = 0
    for j in range(mid):
        a = link[j]
        for k in range(j,mid):
            b = link[k]
            total_2 +=graph[a][b]+graph[b][a]
    
    diff = min(diff,abs(total_1-total_2))

print(diff)

combinations에서 정렬을 해주기 때문에 맨 앞과 맨 뒤를 합치면 완전한 리스트가 만들어진다. ex- [1,2,3]과 [4,5,6]

start팀과 link팀 각각 능력치 합을 구하고, 그 차이를 빼주어 가장 작은 값을 저장하도록 했다.

3. 치킨 배달

링크 - https://www.acmicpc.net/problem/15868

코드

from itertools import combinations
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

#집과 치킨집 좌표
house=[]
chicken = []

for i in range(1,n+1):
    line = list(map(int,input().split()))
    for j in range(len(line)):
        if line[j]==1:
            house.append([i,j+1])
        elif line[j]==2:
            chicken.append([i,j+1])

#m개뽑기
comb = list(combinations(chicken,m))

#모든 집에서 치킨거리 구하기
answer=int(1e9)
for c in comb:
    dist=0
    for hx,hy in house:
        tmp=int(1e9)
        for cx,cy in c:
            tmp = min(tmp,abs(hx-cx)+abs(hy-cy))
        dist+=tmp
    answer = min(answer,dist)
print(answer)

스타트와 링크 문제와 유사하다.
조합을 이용해서 임의의 치킨집을 뽑아두고 연산을 하였다.