오늘의 알고리즘, 소프티어 수퍼바이러스, 강의실 배정

오늘의 알고리즘

소프티어와 함께하는 알고리즘 문제 풀이

수퍼바이러스

문제

수퍼바이러스가 증식한다.

수퍼바이러스는 0.1초당 P배로 증가한다.
수퍼바이러스는 죽지 않는다.
처음에 K마리가 있는 상태에서 N초 후에 수퍼바이러스는 몇 개일까?

입력

K P N

출력

최종 바이러스의 개수를 1000000007로 나눈 나머지

제약조건

1 ≤ K ≤ 10^8 인 정수
1 ≤ P ≤ 10^8 인 정수
1 ≤ N ≤ 10^16 인 정수

파이썬 2초 256MB

풀이

단순히 아래처럼 풀이하면 안된다.

제곱은 O(N)이기 때문에 제약조건에 따라 제한 시간을 초과한다.

print(K * P ** (N*10) % 1000000007)

divide and conquer, 재귀함수를 구현하여 해결한다.

핵심 아이디어는 제곱을 곱셈으로 풀고 절반으로 나누면 나머지 절반과 같은 값을 가져서 O(logN)으로 풀 수 있다는 점이다.

K, P, N = map(int, input().split())

def divide(P, n):
  if n == 1:
    return P

  if n%2:
    return divide(P, (n-1)//2)**2 * P % 1000000007
  return divide(P, n//2)**2 % 1000000007

print((K * divide(P, N*10)) % 1000000007)

추가로 나머지를 구하는 문제에서 결과값을 반환할 때, 나머지를 미리 구하고 반환해도 원래의 나머지와 같다.

수학적으로 증명하자면 아래와 같다.

수식

강의실 배정

문제

하나의 강의실에 최대한 많은 강의를 배정하려고 한다.

강의실은 하나니깐 강의가 겹치면 안된다.
휴식 시간 없이 진행할 수 있어 시작시간과 다음 강의 종료시간이 같을 수 있다.
최대 강의 수를 구하라.

제약조건

1 ≤ N ≤ 10^6 인 정수
1 ≤ 시작 ＜ 종료 ≤ 10^9

파이썬 5초 256MB

입력

강의 개수 N
2번째 줄부터 N+1 줄까지 시작시간, 종료시간이 제시된다.

풀이

전형적인 정렬문제이다.
입력 수 백만에 내장된 정렬 알고리즘을 적용하면 O(NlonN)이므로
넉넉하게 해결할 수 있다.

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
L = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
cnt = 1
cur = L[0]

for l in L[1:]:
  if cur[1] <= l[0]:
    cur = l
    cnt += 1

print(cnt)