1. 각 방에는 여러 개의 스위치가 있습니다. 따라서 매트릭스를 만들어서 다른 방의 스위치 좌표들을 저장합니다
위 입력을 토대로 한 예시 매트릭스입니다. 이 매트릭스는 switchs라고 부르겠습니다.
2. 스위치의 상태(on/off)와 베스가 이동 가능한 방인지를 표현할 매트릭스를 만듭니다.
이 매트릭스는 board라고 부르겠습니다.
불이 꺼진 상태 : 0
불이 켜진 상태 : 1
베스가 이동 가능한 방 : 2
베스는 항상 (1, 1)에서 출발한다고 했으므로, (1, 1)의 초기값은 2입니다.
3. 베스의 출발 지점인 (1, 1)을 queue 리스트에 담습니다.
- queue 리스트에 들어 있는 좌표는 다른 방의 스위치를 탐색하기 위해 사용됩니다.
- queue에 리스트에 값이 없어질 때 까지 4 ~ 4-2-1 과정에 대한 반복문이 수행됩니다.
4. queue에 있는 좌표 (1, 1)을 빼내고, 해당 좌표의 switchs 매트릭스에 있는 모든 다른 방의 스위치를 누릅니다.
- 스위치를 켠 방의 상하좌우를 탐색하여 주변에 2가 있는지 확인합니다.
4-1. 주변에 2가 없다면 board 매트릭스의 해당 좌표에 1을 입력합니다.
(불만 켭니다 : 해당 방에는 베스가 들어갈 수 없습니다.)
4-2. 주변에 2가 있다면 board 매트릭스의 해당 좌표에 2를 입력합니다.
(불이 켜져 있는 인접한 방이므로, 베스가 들어갈 수 있습니다.)
- 주변에 1이 남아 있는 경우를 고려하여, 다시 한 번 상하좌우를 탐색해야 합니다
4-2-1. 상하좌우로 인접한 방에 1이 있는지 확인한 후, 존재한다면 2로 수정합니다.
- 4-2-1번 작업은 BFS 알고리즘이 재귀적으로 수행되어야 합니다.
- 2로 수정된 방의 좌표에서는 switchs에 기록된 정보들의 탐색이 이뤄지지 않았으므로, queue에 담습니다.
* 4-2-1 작업이 재귀적으로 수행되어야 하는 이유
첫 번째 그림은, 기존에 불 켜져있는 방들이 밀집됐지만, 베스가 들어갈 수 없는 방을 표현했습니다.
두 번째 그림에서 (1, 2)에 불이 켜짐으로써 나머지 (2, 2), (3, 2), (3, 3)도 들어갈 수 있는 방으로 변해야 하는 상황이 되었습니다. 따라서 4-2-1 작업은 재귀적으로 수행되어야 합니다. 그 결과는 세 번째 그림과 같습니다.
코드
import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
n, m = map(int, input().split()) # n : n x n의 방을 만듦, m : m개의 데이터를 받음
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
board = [[0] * (n+1) for _ in range(n+1)] # 1: 불 켜짐, 2: 이동 가능
board[1][1] = 2
switchs = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
x, y, a, b = map(int, input().split())
switchs[x][y].append([a, b])
def BFS(x, y):
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 < xx <= n and 0 < yy <= n:
if board[xx][yy] == 1:
board[xx][yy] = 2
queue.append([xx, yy])
BFS(xx, yy)
cnt = 1
queue = deque([[1, 1]])
while queue:
x, y = queue.popleft()
for a, b in switchs[x][y]:
for i in range(4):
aa = a + dx[i]
bb = b + dy[i]
if 0 < aa <= n and 0 < bb <= n:
if board[a][b] == 2:
break
if board[aa][bb] == 2:
cnt += 1
board[a][b] = 2
queue.append([a, b])
BFS(a, b)
break
if board[a][b] == 0:
board[a][b] = 1
cnt += 1
print(cnt)
1. 학생들이 제출한 목록을 "b를 기준으로 오름차순 --> a를 기준으로 내림차순" 한다.
2. 책의 분배 상태를 의미하는 리스트를 한 개 만든다.
- 인덱스는 책의 번호를 의미한다.
- 인덱스 값은 책을 분배했음(1), 분배하지 않음(0)을 의미한다.
3. 학생들이 제출한 범위 내에서 반복문을 진행하고, 책의 분배 상태를 확인한다.
- 분배되지 않은 책을 발견하면, 리스트의 해당 인덱스를 1로 변경한 후 반복문을 종료한다.
* b를 기준으로 오름차순 한 이유
[1, 2]와 [2, 4]의 예제가 존재한다고 가정하자.앞선 학생이 갖는 선택지는 1과 2가 있다.뒷 학생이 갖는 선택지는 2, 3, 4가 있다.
만약 앞선 학생이 1번 책을 선택한다면, 뒷 학생은 온전히 2, 3, 4의 선택지를 갖게 된다.
하지만 만약 앞선 학생이 2번 책을 선택한다면, 뒷 학생은 3, 4의 선택지를 갖게 된다.
또한, [a, b]에서 b는 언제나 a보다 작거나 같다. (a<=b)
따라서 b가 낮은 학생들이 우선순위를 가져야 한다.
* a를 기준으로 내림차순 한 이유
b를 기준으로 오름차순한 상태에서 a를 기준으로 내림차순 한 이유는 다음과 같다.
예를 들어, [2, 3]과 [1, 3]이 존재한다고 하자.
앞선 학생의 경우의 선택지는 2와 3이 있다.
반면에 뒷 학생의 선택지는 1, 2, 3이 있다.
따라서 선택지가 더 적은 [2, 3]을 제출한 학생이 우선순위를 가져야 한다.
즉, a를 기준으로 내림차순 해야 한다.
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
n = int(input())
for _ in range(n):
numBooks, numStudents = map(int, input().split())
queue = [list(map(int, input().split())) for _ in range(numStudents)]
queue.sort(key=lambda x: x[1])
status = [0] * (numBooks+1)
for i in range(numStudents):
for j in range(queue[i][0], queue[i][1]+1):
if status[j] == 0:
status[j] = 1
break
print(sum(status))
4. 단, 회의 시간이 종료되자마자 회의가 시작될 수 있으며, 회의시작 시간과 종료시간이 같을 수 있다.
문제 특징
- 회의가 빨리 끝나면 더 많은 회의를 할 수 있다.
하지만 단순히 회의 종료시간을 기준으로 오름차순을 하게 되면 반례에 걸리게 된다.
예를 들어, [5, 5], [5, 5], [4, 5]가 스케줄로 주어진다고 하자.
그렇다면 우리가 예상하는 답은 [4, 5], [5, 5], [5, 5]이다.
하지만 만약 회의 시작시간이 내림차순으로 되어 있다면 [5, 5], [5, 5], [4, 5]가 출력이 된다.
따라서 "종료시간(오름차순) -> 시작시간(오름차순)"으로 정렬이 이뤄져야 한다.
코드
import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
n = int(input())
heap = []
for _ in range(n):
s, e = map(int, input().split())
heapq.heappush(heap, (e, s))
cnt = 0
before_e = 0
while heap:
e, s = heapq.heappop(heap)
if s >= before_e:
before_e = e
cnt += 1
print(cnt)
1. 3차원 배열에서의 BFS만 구현하면 된다. (기본 2차원 배열에서 배열을 하나 더 추가한 것이다.)
1. 익은 토마토의 좌표를 리스트에 담는다.
2. 익은 토마토를 중심으로 상/하/좌/우/위/아래로 좌표를 이동시킨다.
3. 이동한 좌표가 좌표평면에서 벗어나지 않는다면 계속 진행한다.
4. 이동 전 익은 토마토의 좌표의 값에 1을 더하여 이동 후의 좌표 평면에 1을 더해준다. (매일 주변에 있는 토마토가 익으므로, 좌표평면에 존재하는 값은 "지난 일수"를 의미 한다.)
5. 좌표를 이동함으로써 익게 된 토마토의 좌표를 리스트에 담는다.
6. x, y, z 방향으로 3중 반복문을 실행하여 토마토가 전부 익었는지 확인한다.
- 모두 익지 않았다면 -1을 출력하고 프로그램을 종료한다.
7. 최대 값(mx)을 1로 초기화한다.
- 문제 조건에서 처음부터 토마토가 모두 익었으면 0을 출력하라고 했다.
8. x, y, z 방향으로 3중 반복문을 실행하여, mx와 비교하며 좌표 평면에서 가장 큰 수(익는데 걸린 일수)를 찾는다.
9. mx - 1을 해서 정답을 출력한다.
- 시작 시에 좌표평면의 값이 1이므로, 익는데 걸린 시간에 포함시키지 않는다.
코드
import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def BFS():
while queue:
x, y, z = queue.popleft()
for dx, dy, dz in mv:
xx = x + dx
yy = y + dy
zz = z + dz
if 0 <= xx < col and 0 <= yy < row and 0 <= zz < height and board[zz][yy][xx] == 0:
board[zz][yy][xx] = board[z][y][x] + 1
queue.append([xx, yy, zz])
if __name__ == '__main__':
col, row, height = map(int, input().split())
board = [[list(map(int, input().split())) for _ in range(row)] for _ in range(height)]
mv = ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1))
# 익은 것의 좌표를 찾는다.
queue = deque()
for y in range(row):
for x in range(col):
for z in range(height):
if board[z][y][x] == 1:
queue.append([x, y, z])
BFS()
# 모두 다 익었는지 확인한다.
for y in range(row):
for x in range(col):
for z in range(height):
if board[z][y][x] == 0:
print(-1)
sys.exit()
# 걸린 일수를 출력한다.
mx = 1
for z in range(height):
for y in range(row):
mx = max(mx, max(board[z][y]))
print(mx-1)
이런 경우에는 5kg짜리 봉투를 2개를 사용한 뒤에 나머지를 3kg짜리 봉투에 담아야 합니다.
그렇게 되면 3kg짜리 봉투에 들어갈 수 있는 설탕의 양은 2kg 밖에 되지 않습니다.
즉, 문제에서 요구하는 답을 낼 수 없습니다.
5kg짜리 봉투 1개에만 적당히 소금을 담고, 3kg짜리 봉투를 2개를 사용하여 설탕을 담으면 문제에서 요구하는 정답을 제출할 수 있습니다.
알고리즘
N이 11로 주어진 상황을 가정하고 설명하겠습니다.
1. 5kg짜리 봉투가 허용하는 최대 무게부터 5 단위로 감소시키며, 0까지 반복문을 실행합니다.
2. N에서 5가 허용하는 무게(10, 5, 0)를 뺍니다.
뺀 값은 다시 N에 담습니다.
3. N을 3으로 나눕니다. 이 때 나머지가 0이면, 반복문을 빠져나옵니다.
4. 답으로는 5의 "'배수(2)'가 되는 값 + N/3의 몫"으로 제출합니다. (나머지가 0인 것이 없다면 -1을 답으로 제출합니다)
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
inputData = int(input())
T = inputData//5
answer = -1
for i in range(T, -1, -1):
n = inputData - (5 * i)
a, b = divmod(n, 3)
if b == 0:
answer = i + a
break
print(answer)
- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.
- back을 왼쪽으로 한 칸 움직이자.
3.
- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.
- back을 왼쪽으로 한 칸 움직이자. (back이 front보다 앞으로 가게 되므로 반복문이 종료된다.)
코드
def solution(people, limit):
answer = 0
people = sorted(people)
front = 0
back = len(people)-1
while front < back:
answer += 1
if people[front] + people[back] <= limit:
front += 1
back -= 1
return answer
