[파이썬] 백준 1102 : 발전소 (플레5)

[파이썬] 백준 1102 : 발전소 (플레5)

1102번: 발전소

---

문제

---

풀이

0. 방향성 생각

• dfs로 순회해주면서 가지치기 / 메모제이션으로 시간 단축하기.
• 개수가 다 채워졌으면 다른 발전소를 키지 않는거는 자명한 사실이니까, 개수 체크해주기.

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

def cvt(state):
    on = 0
    string = ''
    for stt in state[::-1]:
        if stt == 'Y':
            string += '1'
            on += 1
        else:
            string += '0'
    return int(string,2),on

n = int(input())
edges = [tuple(map(int,input().split())) for _ in range(n)]
state,on = cvt(input())
p = int(input())

• 입력 받고, cvt변환을 통해서 현재 상태를 int로 바꾸고 몇개가 켜져있는지 카운트.
• 왼쪽부터 0번 ~ N-1번 발전소라서 뒤집어서 시작해주기.
• 체크 못해서 자꾸 1번테케 22 나옴 ㅠ

2. DFS DP

inf = 1e9
answer = inf
dp = [inf]*(1<<n)

def dfs(s,c):
    
    if c >= p:
        return 0

    if dp[s] != inf:
        return dp[s]

    for x in range(n):
        for nx in range(n):
            if s&(1<<x) and not s&(1<<nx):
                dp[s] = min(dp[s],dfs(s|(1<<nx)+edges[x][nx],c+1))
    return dp[s]

answer = dfs(state,on)
print(answer if answer != inf else -1)

• p개 이상 켜졌으면 탐색할 필요 x
• 재사용은 dp[s]로 시간 줄이기

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

def cvt(state):
    on = 0
    string = ''
    for stt in state[::-1]:
        if stt == 'Y':
            string += '1'
            on += 1
        else:
            string += '0'
    return int(string,2),on

n = int(input())
edges = [tuple(map(int,input().split())) for _ in range(n)]
state,on = cvt(input())
p = int(input())

inf = 1e9
answer = inf
dp = [inf]*(1<<n)

def dfs(s,c):
    
    if c >= p:
        return 0

    if dp[s] != inf:
        return dp[s]

    for x in range(n):
        for nx in range(n):
            if s&(1<<x) and not s&(1<<nx):
                dp[s] = min(dp[s],dfs(s|(1<<nx)+edges[x][nx],c+1))
    return dp[s]

answer = dfs(state,on)
print(answer if answer != inf else -1)

 

코멘트

메모제이션이나 최적화를 너무 못한다.... 더 연습하기

원래 끝 상태에 도달하면 최솟값 answer를 변경시키는 식으로 풀었다. (켜진 개수가 p개 이상이면 갱신하고 재귀 탈출)

푸는건 10분 정도 걸린거같은데 최적화를 못해서 시간 메모리 초과 ㅠ