25.03.19 코딩테스트 대비

BOJ 15686. 치킨 배달

---

https://www.acmicpc.net/problem/15686

 

 

내 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

city = []
houses = []
chicken = []

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

answer = float('inf')
def backtracking(start, now, chosen):
    global answer
    if now == m:
        total = 0
        for house in houses:
            distance = float('inf')
            for c in chosen:
                distance = min(distance, abs(house[0] - chicken[c][0]) + abs(house[1] - chicken[c][1]))
            total += distance

        answer = min(answer, total)
        return

    for i in range(start, len(chicken)):
        if i not in chosen:
            chosen.append(i)
            backtracking(i+1, now + 1, chosen)
            chosen.pop()

backtracking(0, 0, [])

print(answer)

 

backtracking을 통해 m개의 치킨집을 골랐을 때, 도시 치킨 거리를 모두 구했다.

 

그 중 제일 작은 값을 answer에 저장하고 출력하여 정답을 맞출 수 있었다.

 

 

내 제출

 

 

BOJ 17070. 파이프 옮기기 1

---

https://www.acmicpc.net/problem/17070

 

 

내 코드

import sys

input = sys.stdin.readline

n = int(input())
board = []

for _ in range(n):
    board.append(list(map(int, input().split())))

count = 0
def dfs(x, y, state):
    global count
    if x == n-1 and y == n-1:
        count += 1
        return

    if state == 0:
        if y == n-1:
            return
        if 0 <= y + 1 < n and board[x][y+1] == 0:
            dfs(x, y+1, 0)
        if 0 <= x + 1 < n and 0 <= y + 1 < n and board[x+1][y] == 0 and board[x][y+1] == 0 and board[x+1][y+1] == 0:
            dfs(x+1, y+1, 2)
   
    elif state == 1:
        if x == n-1:
            return
        if 0 <= x + 1 < n and board[x+1][y] == 0:
            dfs(x+1, y, 1)
        if 0 <= x + 1 < n and 0 <= y + 1 < n and board[x+1][y] == 0 and board[x][y+1] == 0 and board[x+1][y+1] == 0:
            dfs(x+1, y+1, 2)
   
    else:
        if 0 <= y + 1 < n and board[x][y+1] == 0:
            dfs(x, y+1, 0)
        if 0 <= x + 1 < n and board[x+1][y] == 0:
            dfs(x+1, y, 1)
        if 0 <= x + 1 < n and 0 <= y + 1 < n and board[x+1][y] == 0 and board[x][y+1] == 0 and board[x+1][y+1] == 0:
            dfs(x+1, y+1, 2)

dfs(0,1,0)
print(count)

 

처음에는 bfs로 풀었다가 시간 초과가 계속나서 dfs로 바꿔서 코드를 제출했다...

 

근데 이 코드 역시 pypy3로 해야 제출이 되는 것 같다.

 

dp로도 이 문제를 풀 수 있는 것 같은데, 다시 한번 풀어봐야 될 것 같다.

 

내 제출

 

 

 

BOJ 30805. 사전 순 최대 공통 부분 수열

---

 

 

내 코드

import sys

input = sys.stdin.readline


n = int(input().strip())
a = list(map(int, input().split()))

m = int(input().strip())
b = list(map(int, input().split()))

common = set(a) & set(b)

answer_len = 0
answer = ""
while common:
    max_num = max(common)
    answer += str(max_num) + " "
    answer_len += 1

    a = a[a.index(max_num)+1:]
    b = b[b.index(max_num)+1:]

    common = set(a) & set(b)
    
print(answer_len)
if answer_len != 0:
    print(answer)

 

처음에는 LCS를 통해 푸는 유형인가 했는 데 최장 수열이 아닌 사전 순으로 가장 나중인 수열을 출력하는 문제라서 Greedy하게 풀면 될 것 같았다.

 

일단 a와 b의 공통 수 common을 set(a) & set(b)를 통해 구한다.

 

그리고 while 문을 통해 조건을 만족하는 해를 구한다.

 

먼저 현재 common에서 제일 큰 수를 구하고 answer += str(max_num) + " "을 해준다. answer_len 역시 +1를 해준다.

 

그 다음으로 a와 b도 제일 큰 수 뒤에 있는 리스트로 바꿔준다.

 

예를 들어, 현재 common이 {1,7,3},  a = [1, 9, 7, 3] , b = [1, 8, 7, 5, 3]이고 common의 제일 큰 수가 7이기 때문에

answer = "7 "이 되고, answer_len = 1이 된다. 또한, a = [3], b = [5, 3]이 된다.

 

그리고 이를 다시 set(a) & set(b)를 하면 common은 [3]이 된다.

그러면 다시 answer = " 7 3 "이 되고 answer_len =2가 된다.

a = [], b =[] 이되고 이를 다시 set(a) & set(b)를 하면, 이제 공통 수가 없으니 반복문을 탈출하게 된다.

 

마지막에는 answer_len과 answer를 출력하고 정답을 맞출 수 있었다.

 

 

내 제출