25.03.21 코딩테스트 대비

BOJ 16236. 아기 상어

---

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

 

내 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

area = []
for i in range(n):
    area.append(list(map(int, input().split())))
    for j in range(n):
        if area[i][j] == 9:
            start = (i, j)
            area[i][j] = 0

def bfs(start, size):
    visited = [[0]*n for _ in range(n)]
    q = deque([start])
    visited[start[0]][start[1]] = 1
    eat = []
    while q:
        x, y = q.popleft()
        for move in moves:
            nx = x + move[0]
            ny = y + move[1]

            if 0 <= nx < n and 0 <= ny < n:
                if area[nx][ny] <= size and visited[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                    if 0 < area[nx][ny] < size:
                        eat.append((nx, ny, visited[nx][ny]-1))
    return eat

size = 2
eat = 0
time = 0
moves= [(0, 1), (0, -1), (1, 0), (-1, 0)]

while True:
    result = bfs(start, size)
    if not result:
        print(time)
        break
    result.sort(key=lambda x: (-x[2], -x[0], -x[1]))
    x, y, t = result.pop()
    time += t
    area[x][y] = 0
    eat += 1
    if eat == size:
        size += 1
        eat = 0
    start = (x, y)

간단한 bfs 문제인 줄 알았는데 생각보다 어려운 문제였다..

 

• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

정렬을 통해 위 조건을 만족하는 물고기를 먹는다고 판단했다.

 

위 조건만 만족할 수 있으면 나머지는 쉽게 구현하여 풀 수 있다.

 

내 제출

 

 

BOJ 11054. 가장 긴 바이토닉 부분 수열

---

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

 

 

내 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n
dp1 = [1] * n

for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

answer = 0
for i in range(n):
    answer = max(answer, dp[i] + dp1[i] - 1)

print(answer)

 

증가하는 dp 배열과 감소하는 dp 배열 2개를 만들어 값을 저장하고 max(answer, dp[i] + dp1[i] - 1)를 통해 정답을 구할 수 있다.

 

이 문제를 풀기 전에 BOJ 11053. 가장 긴 증가하는 부분 수열을 풀어보면 도움이 될 것 같다.

BOJ 11053 문제의 코드는 다음과 같다.

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [1]*n
for i in range(1,n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i],dp[j]+1)
            
print(max(dp))

 

 

 

내 제출

 

 

 

BOJ 2470. 두 용액

---

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

 

 

내 코드

import bisect
import sys

input = sys.stdin.readline

n = int(input())
features = list(map(int, input().split()))
features.sort()

diff = float('inf')
answer = [0, 0]
for i in range(n):
    pos= bisect.bisect_left(features, -features[i])
    if pos != n:
        if pos != i and diff > abs(features[i] + features[pos]):
            diff = abs(features[i] + features[pos])
            answer = [features[i], features[pos]]
        if pos-1 != i and diff > abs(features[i] + features[pos-1]):
            diff = abs(features[i] + features[pos-1])
            answer = [features[i], features[pos-1]]
    else:
        if pos-1 != i and diff > abs(features[i] + features[pos-1]):
            diff = abs(features[i] + features[pos-1])
            answer = [features[i], features[pos-1]]

print(*sorted(answer))

처음에는 이진탐색을 통해 문제를 해결했다.

 

features를 정렬시켜주고 각 feature[i]의 -feature[i]와 가까운 요소의 위치를 구해 실제 features[i]와 features[pos]를 더해 절대값을 취한 값이 0과 가까우면 answer를 업데이트해 나갔다.

 

이진탐색 말고도 투포인터를 이용해 해결할 수도 있다.

left와 right를 0과 n-1로 설정해주고

left < right일 동안 features[left] + features[right]값을 구한다. 

이 값이 0보다 크다고 한다면 right를 -1해주고 아니면 left를 +1 하면서 계속 features[left] + feature[right] 값을 구한다.

그 중 제일 0과 가까운 값을 answer에 저장하고 출력하여 정답을 맞출 수 있다.

 

투포인터를 이용한 코드는 다음과 같다.

import sys

input = sys.stdin.readline

n = int(input())
features = list(map(int, input().split()))
features.sort()

left = 0
right = n-1

min_diff = float('inf')
answer = [0, 0]
while left < right:
    diff = features[left] + features[right]
    if min_diff > abs(diff):
        min_diff = abs(diff)
        answer = [features[left], features[right]]
    
    if diff > 0:
        right -= 1
    else:
        left += 1

print(*answer)

 

 

내 제출