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
- 스도쿠의 각 칸에는 가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수가 존재하지 않아야 한다.
본 문제를 풀이할 때 주의사항이 있다.
"가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수"를 고려하여 문제를 풀었을 때 답이 나오지 않는 경우가 존재한다.
그럴 때는 이전 칸으로 돌아가서 조건에 맞는 다른 수로 수정해야 한다.
따라서 이 문제는 백 트래킹을 사용해야 한다.
알고리즘
1. 스도쿠에 빈 공간(0)이 있는지 확인한다.
2. 빈 공간이 없으면 스도쿠가 완성됐으므로 종료한다.
3. 빈 공간이 있으면 빈 공간(col, row)이 어딘지 말한다.
4. 빈 공간에 어떤 값(1~9)이 들어갈 수 있는지 탐색한다.
- 찾았다면 스도쿠에 채워넣는다.
- 채워넣을 수 있는 게 없다면 백 트래킹 한다.
스도쿠에 빈 공간 확인하기
1. 스도쿠 전체를 탐색하며 빈 공간(0)이 발견되면 해당 좌표를 리턴한다.
2. 스도쿠에서 빈 공간이 발견되지 않으면, None을 리턴한다.
빈 공간에 들어갈 수 있는 값인지 식별하기
빈 공간에 들어갈 수 있는 값인지 식별하기 위해서는 "가로 / 세로 / 3 x 3 박스"를 탐색해야 한다.
1. 가로 탐색
스도쿠의 column을 고정시키고 row 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
2. 세로 탐색
스도쿠의 row을 고정시키고 col 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
3. 3 x 3 박스 탐색
1. 탐색이 시작될 지점을 계산한다
2. 탐색시작 지점에서부터 3 x 3 지점을 탐색한다.
1. (7, 4) 지점이 속한 박스 영역의 시작 지점을 찾는다고 가정하자.
2. 왼쪽 그림의 경우 박스의 시작 지점은 (6, 3)이다.
3. 박스 영역의 시작 지점을 찾는 공식은 (컬럼좌표//3 * 3, 로우좌표//3 *3)이다.
("a//b"는 a와 b를 나눴을 때 몫과 나머지 중에 몫만 출력한다)
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def pretty_print():
for i in range(9):
for j in range(9):
print(board[i][j], end='')
print()
def find_empty():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None, None
def valid(col, row, val):
# 가로 축 점검
for i in range(9):
if board[col][i] == val:
return False
# 세로 축 점검
for i in range(9):
if board[i][row] == val:
return False
# 3x3 박스 점검
box_col = col // 3 * 3
box_row = row // 3 * 3
for i in range(3):
for j in range(3):
if board[box_col+i][box_row+j] == val:
return False
return True
def solution():
col, row = find_empty()
if col is None:
return True
else:
for i in range(1, 10):
if valid(col, row, i):
board[col][row] = i
if solution():
return True
board[col][row] = 0
return False
if __name__ == '__main__':
board = [list(map(int, input())) for _ in range(9)]
solution()
pretty_print()
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def passOrNot(v, usedIdx):
global mn
for i in range(4):
if req[i] > v[i]:
return False
mn = v[4]
mnIdx.clear()
mnIdx.extend(usedIdx)
return
def DFS(L, v, usedIdx):
global mn
if v[4] >= mn:
return
if passOrNot(v, usedIdx):
return
if L == n:
return
else:
usedIdx.append(L+1)
for i in range(5):
v[i] += data[L][i]
DFS(L + 1, v, usedIdx)
usedIdx.pop()
for i in range(5):
v[i] -= data[L][i]
DFS(L + 1, v, usedIdx)
if __name__ =='__main__':
n = int(input())
req = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(n)]
mn = 9999999
mnIdx = []
res = DFS(0, [0]*5, [])
if mn == 9999999:
print(-1)
else:
print(mn)
for i in mnIdx:
print(i, end=' ')
(4-1) data[3]에는 비교대상이 없으므로 dy, queue 리스트의 변화가 없습니다.
(5) q에 있는 (8,3)은 이미 dy[3]보다 크므로, 비교/갱신을 진행하지 않고 꺼냅니다.
(6) 답을 리턴합니다.
- 1000000을 제외하고 가장 큰 값은 최종 감염시간을 나타냅니다 : 6
- 1000000을 제외한 값의 개수는 감염된 컴퓨터의 수를 나타냅니다 : 3
dy
문제풀며 작성한 구상도
문제 풀면서 작성했던 구상도입니다. 혹시 위의 설명으로 부족하신 분은 참고해서 봐주세요
코드
import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
numTestcase = int(input())
for _ in range(numTestcase):
n, d, c = map(int, input().split()) # n : 컴퓨터 수, d : 의존성 수, c : 감염원
data = [[] for _ in range(n+1)] # '인덱스'는 의존받는 대상(b), '값'은 [(x초 후 감염, 의존하는 대상(a))]
for _ in range(d):
a, b, s = map(int, input().split()) # 감염 방향: b -> a, s초 후 감염
data[b].append((s, a))
# 다익스트라 알고리즘
dy = [100000000] * (n+1) # 몇 초 후에 감염되는지 저장
dy[c] = 0 # 감염원(c)은 0초 후에 감염
q = [(0, c)]
while q:
timePassed, infectedCp = heapq.heappop(q)
if dy[infectedCp] < timePassed:
continue
for s, a in data[infectedCp]:
if dy[a] > s + timePassed:
dy[a] = s + timePassed
heapq.heappush(q, (s+timePassed, a))
time = -1
nCp = 0
for i in range(1, n+1):
if dy[i] != 100000000:
time = max(time, dy[i])
nCp += 1
print(nCp, time)
