허진혁

1. 카펫

접근방법

brown 가로 ≥ yellow 가로 + 2
brown 세로 ≥ yellow 세로 + 2
노란색을 기준으로 코드를 짜야겠다 !!

너비 * 높이 = total = brown + yellow

노란색의 높이를 1부터 height ≤ width까지 반복한다.

2 * 가로길이 + 2 * 세로길이 = brown 수 + 4

def solution(brown, yellow):
    answer = []
    # brown 가로 >= yellow 가로+2
    # brown 세로 >= yellow 세로+2
    total = brown + yellow
    for height in range(1, total+1):
        if (total / height) % 1 == 0:
            width = total / height
            if width >= height:
                if 2*width + 2*height == brown+4:
                    answer = [width, height]
    return answer
Python
복사

1	1	1	1	1	1
1	0	0	0	0	1
1	0	0	0	0	1
1	0	0	0	0	1
1	0	0	0	0	1
1	0	0	0	0	1
1	0	0	0	0	1
1	1	1	1	1	1

2. 피로도

접근방법

 그리디

최소피로도가 높고, 소모피로도가 작은 순으로 정렬 (람다식사용)

이렇게 할 경우 반례가 존재할 수 있음 (최소피로도, 소모피로도가 둘 다 높은 경우)

완탐

던전을 던전의 갯수만큼 순열을 생성해서 (nPr)

각 던전을 돌 때 1. 최소피로도 보다 높을 경우 돌 수 있음 2. 던전에 입장하면 power가 깎임

방금 순회한 결과값 갯수가 이전 순회한 결과값 갯수 보다 크면 answer에 할당

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    dungeon_cnt = len(dungeons)
    
    # 순열을 통해 모든 경우의 수 확인
    for dungeon in permutations(dungeons, dungeon_cnt):
        power = k
        cnt = 0
        # 순열을 통해 나온 던전 챌린지 시작
        for go in dungeon:
            if power >= go[0]:
                power -= go[1]
                cnt += 1
            # 지금까지의 cnt와 보다 큰 cnt가 나오면 재할당
            if answer < cnt:
                answer = cnt
                
    return answer
Python
복사

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer
Python
복사

3. 전력망을 둘로 나누기

접근방법(BFS)

bfs 공식을 만든다

1. deque 선언 2. 방문처리를 위한 visited[False] * (n+1) 3. 노드(선입된 값)을 빼면서 인접한 노드 방문처리 4. 시작하는 곳을 True로 바꾸고 while queue: 실행

2개의 전력망은 최소 1개씩 들고 있기에 두 전력망의 차의 절댓값은 최소 2이다 (answer = 2)

인접한 노드들을 각각 배열에 추가

d. bfs의 시작점 start를 설정하기 —> 배열에 값이 있는 경우 start(= 인접한 곳이 있을 경우)

e. 두 전력망의 차이(절대값 abs사용)

from collections import deque


def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    cnt = 0

    while queue:
        x = queue.popleft()
        cnt += 1

        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


    return cnt

def solution(n, wires):
    answer = n-2 # 최대 n-2개

    for i in range(len(wires)):
        temps = wires[:]
        graph = [[] for _ in range(n+1)]
        visited = [False] * (n+1)
        temps.pop(i)

        # 연결된 곳들 파악
        for wire in temps:
            x, y = wire
            graph[x].append(y)
            graph[y].append(x)
        
        # start 변경로직
        for idx, check in enumerate(graph):
            if check != []: 
                start = idx
                break
        
        # 개수 
        first_cnts = bfs(graph, start, visited)
        second_cnts = (n - first_cnts)

        if abs(first_cnts - second_cnts) < answer:
            answer = abs(first_cnts - second_cnts)


    return answer



graph = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

print(solution(9, graph))
Python
복사