백준 13334 철로
사람들의 house, office 간 거리(선분)가 주어지고
깔아야하는 철로 길이가 주어진다.
철로 안에 최대한 (house <-> office) 선분을 꽉꽉 집어넣으면 되는 문제다.
우선 철로 길이보다 거리가 먼 선분들은 쓸모가 없으므로 탐색하면서 걸러주고
걸러진 선분들을 작은 숫자가 앞에 가게 해서 새로운 리스트에 선분들을 append 해준다.
(house, office 순서로 위치 좌표가 주어지는데 house 위치가 더 큰 값(오른쪽)인 경우가 있기 때문. 하우스 오피스 둘중 어디가 왼쪽이고 오른쪽이고는 중요하지 않기 때문에 작은 숫자가 왼쪽 큰 숫자가 오른쪽으로 오게 세팅해준다.)
그런 다음 오른쪽 좌표 숫자를 기준으로 리스트를 다시 오름차순으로 정렬해준다.
for 문을 돌리면서 heappush를 하는데, 해당 회차의 선분 오른쪽 좌표에서 d(철로 길이)를 뺀 값보다 heap에 들어간 선분의 왼쪽 좌표의 최솟값이 더 작다면, heappop을 해준다.
(해당 회차 선분 오른쪽 끝부터 철로를 깔았을 때, heap에 들어있는 선분의 가장 왼쪽 끝 값이 삐져나왔다는 뜻이므로 제거하는 것.)
위 과정을 거치면서 heap의 길이와 ans를 비교(max 메소드 사용)해서 더 큰 값으로 계속 업데이트 해준다.
어떻게 아이디어를 떠올리고 문제에 적용하냐가 중요한 것 같다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
lines_init = [list(map(int, input().split())) for i in range(N)]
d = int(input())
ans = 0
lines = []
heap = []
for line in lines_init:
h, o = line
if abs(h - o) <= d: #하우스 <-> 오피스 간 거리가 d보다 작다면
lines.append(sorted(line)) # 작은 숫자가 앞에 가게 해서 lines에 집어넣음.
lines.sort(key=lambda x:x[1]) # 오른쪽 수(큰 수) 기준으로 정렬함.
for line in lines:
# 힙 최솟값이 line의 오른쪽 숫자에서 d를 뺀 것보다 작을 때
# 즉, line의 오른쪽 끝에서 d 선로를 깐 범위를 벗어났을 때,
# 제외시킨다.
while heap and heap[0][0] < line[1] - d:
heappop(heap)
heappush(heap, line)
# heap이 그전 heap보다 내용물이 많으면,
# 선로 안에 더 많은 선분이 들어있는 것이므로 정답으로 업데이트 해준다.
ans = max(ans, len(heap))
print(ans)3190 뱀
사과를 먹으면 몸 길이가 늘어나는 뱀이 자기 자신의 몸이나 벽에 부딪히면 죽는 게임이다.
꼬리를 먼저 자르고 머리를 이동시키는 게 핵심 로직인듯 하고
시작 좌표가 1,1 이고 사과 위치도 배열 인덱스가 아닌 좌표값을 쓰므로
N+2를 한변으로 하는 테두리를 만들어서 1을 채워놓고 만들면 좀 더 직관적으로
코드를 짤 수 있는 것 같다.
from collections import deque
N = int(input())
board = [[0] * (N+2) for _ in range(N+2)] # 테두리를 추가하여 보드 생성
for i in range(N+2):
board[0][i] = 1 # 가장 윗줄 채우기
board[N+1][i] = 1 # 가장 아랫줄 채우기
board[i][0] = 1 # 가장 왼쪽줄 채우기
board[i][N+1] = 1 # 가장 오른쪽줄 채우기
K = int(input())
apples = []
for _ in range(K):
row, col = map(int, input().split())
board[row][col] = 2 # 사과 위치 표시
l = int(input())
turns = []
for _ in range(l):
X, C = input().split()
turns.append((int(X), C))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 동, 남, 서, 북
direction = 0 # 초기 방향은 동쪽
snake = deque([(1, 1)]) # 뱀의 초기 위치
time = 0
turn_index = 0
while True:
time += 1
row, col = snake[-1]
dr, dc = directions[direction]
nr, nc = row + dr, col + dc
if board[nr][nc] == 1: # 벽 또는 몸에 부딪힌 경우
break
if board[nr][nc] == 0: # 빈칸인 경우
tail_row, tail_col = snake.popleft() # 꼬리를 자름
board[tail_row][tail_col] = 0 # 꼬리가 있던 자리를 비움
snake.append((nr, nc)) # 머리를 다음 칸에 위치시킴
board[nr][nc] = 1 # 머리가 있는 자리를 뱀의 몸통으로 표시
# (사과 먹은 경우는 꼬리를 안자르므로 길이가 늘어남.)
# 방향 전환
if turn_index < len(turns) and time == turns[turn_index][0]:
direction_char = turns[turn_index][1]
if direction_char == 'L':
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
turn_index += 1
print(time)코드가 좀 길지만 N+2 길이의 테두리를 1로 채워놓고 뱀의 방향을 어떻게 표현할지만 잘 구현하면 크게 어렵지는 않은 것 같다. (라고 말했지만 아직 혼자 힘으로 떠올려서 풀기는 버겁다..)
