1931 회의실 배정
정말 막막했던 문제였는데, key point는 2가지 정도였다고 본다.
1) 회의 시간이 짧은 게 중요
2) 회의가 끝나는 시간이 서로 같다면, 회의 시작 시간으로 정렬. 왜냐하면 1~2와 2~2도 가능하기 때문.
그래서 일단 회의 시작 시간으로 정렬하고, 끝나는 시간에 대해 한번 더 정렬을 하면 2번조건을 만족하면서 회의 시간이 짧은 게 위로 올라온다고 생각했다. 이를 lambda함수로 정렬했고 가장 위로 정렬된 회의를 일단 한다고 가정해 cnt를 1로 놓고 시작했다. 그래서 처음 회의가 끝나는 시간이 다음회의가 시작되는 시간보다 "작거나 같을 때" 회의를 할 수 있으므로 cnt를 1 늘려주고, 새로운 회의로 다시 비교를 하기 위해 end에 넣어주었다. 이를 반복한다.
n = int(input())
room_check = []
for i in range(n):
a,b = map(int, input().split())
room_check.append([a,b])
room_check.sort(key=lambda x:x[0])
room_check.sort(key=lambda x:x[1])
cnt = 1
end = room_check[0][1]
for i in range(1, n):
if end <= room_check[i][0]:
cnt += 1
end = room_check[i][1]
print(cnt)
13305 주유소
핵심은 지금 주유소에서 다음 이동거리까지 고려해서 주유를 하느냐 마느냐 였다. 그래서 만약에 처음 시작하는 주유소 가격이 1원이면 총 이동거리만큼 모두 주유를 하고 시작하는 맥락이었다.
일단 시작할 땐 기름이 없으므로 무조건 넣고 시작한다. 그래서 처음 기름가격이 비교대상이 된다. 처음 기름가격보다 그다음 기름가격이 싸다면, 미리 주유할 필요 없으므로 딱 처음에 이동할 거리만큼만 주유하고 그 다음 주유소에서 주유한다. 이 과정을 계속 반복하게 된다. 그런데 만약, 다음 주유소 가격이 지금 주유소 가격보다 비싸다면?? 그렇다면 미리 그 다음 이동거리만큼 주유를 하고 가는 것이다. 그 다음 비교를 했는데 또 비싸다면 또 미리 주유하면 된다. 이렇게 계속해서 마지막까지 비교하는데, for문이 n-1만큼만 도는 이유는 마지막에 가서 주유할 필요가 없으므로 마지막 주유가격은 생각하지 않는 것이다. // 그래서 주유가격*이동거리를 해서 결과에 누적해주는데, 이때 유일한 변수는 주유가격이므로 주유가격만 계속해서 비교하면서 바꿔주면 된다.
n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))
m = costs[0]
result = 0
for i in range(0, n-1):
if costs[i] < m:
m = costs[i]
result += m * roads[i]
print(result)
1904 01타일
일단 tile을 조건의 범위까지 고려해서 선언해주는데, 마지막에 1이 추가돼서 tile=[0]*1000001인 이유는 이 문제에서 0번째는 고려하지 않고 1번째에 1을 넣고 2번째에 2를 넣고 ... 처럼 진행되기 때문에 1만큼 추가로 공간을 배정해주었다.
이 문제가 dp 문제라는 것을 파악하기 굉장히 어려울 수도, 반대로 굉장히 쉬웠을 수도 있는데 tile을 1 2 3 4정도까지만 가도 바로 피보나치임을 파악하고 tile[3] = tile[2] + tile[1]로 풀 수 있었다. 하지만 처음부터 1 00 11 001 100 111 .... 로 진행했다면 00과 1의 위치를 어디로 배정해야되는지 고민하며 dp임을 파악하기 어려웠을 것 같다.
핵심은 0과 1이라는 상당히 이분법적인 상황을 이용하는 것이었다. 바로 시작하는 숫자가 0인지 1인지를 나누어서 생각하는 것인데, 이때 0은 반드시 00처럼 붙어서 이동함을 이용한다. 만약 5번째라면 숫자가 5개가 들어가는 것인데, 여기서 나누어 생각해보면 00???와 1????가 된다. 즉, 우리는 ?가 3개일때와 4개일때만 고려하면 된다. 이 안에서 다시 00과 1을 어떻게 넣는지 생각하면 되는데, 이 구조가 바로 dp라는 것이다. 7일때도 마찬가지로 00?????와 1??????으로 나누어지므로 ?가 6개일때, 5개일때를 생각하면 된다. 바로 0이 붙어있다는 것때문에 반드시 n = n-1 + n-2 구조로 귀결된다. 따라서 이를 우리가 아는 피보나치 식으로 써주면 코드와 같다.
여기서 15746이라는 괴상한 숫자의 나머지로 넣어주는 이유는 피보나치 수가 워낙 조금만 지나도 확 커지므로 뒤로가면서 그것을 다 담지못해 메모리초과가 날까봐 해놓은 것으로 추정된다.
n = int(input())
tile = [0] * 1000001
tile[1] = 1
tile[2] = 2
for i in range(3, n+1):
tile[i] = (tile[i-1] + tile[i-2])%15746
print(tile[n])
