방구석프로의 이야기

https://www.acmicpc.net/problem/2792

문제 해결을 위한 과정

이 문제의 경우 N의 범위가 10^9 이므로 단일 for문으로 해결하려 해도 시간초과 판정을 받는 문제임을 알 수 있습니다. (파이썬의 경우 1초에 20,000,000번 연산을 한다 가정) 따라서 이분 탐색으로 진행합니다. 문제의 조건에서 보석을 받지 못하는 학생이 있어도 됨을 말했으므로 나눠준 보석을 받은 학생수가 N명보다 적어도 됩니다. 또한 같은 색상의 보석만 가져간다라는 조건이 있는데 이는 특별하게 고려하지 않아도 이분탐색 특성상 무조건 같은 색상의 보석만 준다는 것을 알 수 있습니다. 과정은 다음과 같습니다.

1) 보석 수 // 나누어 줄 보석 수 => 몫만큼 나누어준 학생수가 됨

2) 보석 수 % 나누어 줄 보석 수 => 나머지가 존재하면 1명의 학생에게 나누어 줄 수 있음.

소스코드

n, m = map(int, input().split())
arr = []
for _ in range(m):
  arr.append(int(input()))

arr.sort()
ans = int(1e9)

left = 1
right = arr[m-1]

while True:
  if left > right:
    break
  mid = (left + right) // 2
  temp = 0
  for i in range(m):
    temp += arr[i] // mid
    if arr[i] % mid != 0:
      temp += 1
  if temp > n:
    left = mid + 1
  else:
    ans = min(ans, mid)
    right= mid - 1
    
print(ans)

https://www.acmicpc.net/problem/2805

문제 해결을 위한 과정

이 문제의 경우 나무의 수 및 길이가 각각 1,000,000 2,000,000,000 이므로 일반적인 방법으로는 문제를 해결할 수 없습니다. 즉 이분탐색을 진행해야 함을 알 수 있습니다. left를 1, right를 배열의 마지막 값으로 둔 뒤 이분탐색을 진행하면 쉽게 해결할 수 있습니다. 

단 이분탐색은 항상 리스트가 정렬 되어야 합니다. 따라서 오름차순으로 먼저 정렬한 뒤 위의 과정을 합니다.

소스코드

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ans = 0

left = 1
right = arr[n-1]

while True:
  if left > right:
    break
  mid = (left + right) // 2
  temp = 0
  for i in range(n):
    if arr[i] - mid >= 0:
      temp += arr[i] - mid
  if temp >= m:
    ans = max(ans, mid)
    left = mid + 1
  else:
    right = mid - 1

print(ans)

https://www.acmicpc.net/problem/1654

문제 해결을 위한 과정

이 문제의 경우 이분 탐색을 이용하면 해결할 수 있는 문제였습니다. 다만 mid = left + right // 2 이렇게 만들어진 mid로 나누는 과정에서 런타임 에러 (ZeroDivisionError)를 받을수 가 있습니다. 따라서 항상 변수로 나누는 경우는 그 변수가 zero가 될 수 있는지 가능성을 확인해보아야 합니다. 

소스코드

n, k = map(int, input().split())
arr = []
for _ in range(n):
  arr.append(int(input()))
arr.sort()
left = 1
right = arr[n-1]
ans = 0

while True:
  if left > right:
    break
  mid = (left + right) // 2
  cnt = 0
  for i in range(n):
    cnt += arr[i] // mid
  if cnt >= k:
    ans = max(ans, mid)
    left = mid + 1
  else:
    right = mid - 1

print(ans)

https://www.acmicpc.net/problem/16953

문제 해결을 위한 과정

이 문제의 경우 bfs를 이용하면 해결할 수 있는 문제였습니다. 다만, visited 배열을 만들게 되면 10^9 * 4B = 4000MB 이므로 배열을 생성해서는 안됩니다. 따라서 배열을 생성하지 않고 단순하게 큐에 삽입이 될 수가 b와 같은지를 확인하면 됩니다. 

소스코드

from collections import deque

a, b = map(int, input().split())
q = deque()
q.append(a)
ans = int(1e9)
cnt = 1

while q:
  length = len(q)
  for _ in range(length):
    v = q.popleft()
    for i in range(2):
      if i == 0:
        nv = 2 * v
      else:
        nv = int(str(v) + str(1))
      if nv == b:
        ans = cnt
        break
      if nv <= b:
        q.append(nv)
  cnt += 1

if ans == int(1e9):
  print(-1)
else:
  print(ans + 1)

https://www.acmicpc.net/problem/2217

문제 해결을 위한 과정

이 문제의 경우 단일 for문으로 쉽게 해결할 수 있었습니다. 먼저 입력받은 로프를 오름차순으로 정렬하는게 가장 중요합니다. 문제 어디에도 오름차순으로 입력이 된다는 말이 없기 때문에 먼저 오름차순 정렬을 해줍니다. 그 후 각 로프에 현재 로프의 개수를 곱하면서 구해지는 무계중 최대값을 구합니다. 

소스코드

n = int(input())
arr = []
for _ in range(n):
  arr.append(int(input()))
arr.sort()
ans = 0

for i in range(n):
  temp = arr[i] * (n-i)
  if ans < temp:
    ans = temp
print(ans)

백준 알고리즘 1931: 회의실 배정 (Python)

문제 해결을 위한 과정

이 문제는 일반적인 그리디를 이용한 방법으로는 해결할 수 없습니다. 그 이유는 그리디를 이용한 방법은 각 동전끼리 배수 관계를 가지고 있어야 합니다. ex) 1, 10, 100, 1000

이 문제의 예시를 보면 1, 5 12 등 배수 관계가 아니므로 dp를 이용해야 함을 알 수 있습니다.

과정을 설명하면 다음과 같습니다.

2 9

1

5 

를 예시로 하겠습니다.

1. dp 배열 선언 단, 0번째는 0으로 선언 나머지는 INF(1,000,000,000)로 선언

2. 첫 번째 동전을 기준으로 for문을 돌리면서 해당 금액이 이전 동전 + 1개로 가능한지 확인

이 경우는 각 금액이 1원으로 무조건 가능하기 때문이다.

3. 두번째 동전을 기준으로 for문을 돌리면서 해당 금액이 이전 동전 + 1개로 가능한지 확인

이 경우는 5원 => 5원, 6원 => 1 + 5원, 7원 => 1 + 1 + 5원, 8원 => 1 + 1+ 1 + 5원, 9원 1 + 1 + 1 + 1 + 5원으로 가능하기 때문이다.

소스코드

n, k = map(int, input().split())
coins = []
for _ in range(n):
  coins.append(int(input()))
INF = int(1e9)
dp = [INF] * (k + 1)
dp[0] = 0

for coin in coins:
  for i in range(1, k + 1):
    if i - coin >= 0:
      dp[i] = min(dp[i], dp[i-coin] + 1)

if dp[k] == INF:
  print(-1)
else:
  print(dp[k])

https://www.acmicpc.net/problem/1931

문제 해결을 위한 과정

이 문제는 정렬을 이용하면 해결할 수 있었습니다. 끝나는 시간을 기준으로 오름차순으로 정렬을 하면 됩니다. 다만 이 경우 시작 지점 역시 오름차순을 해야 한다는 점이 있습니다. 또한 시작과 동시에 종료인 경우도 한가지 경우로 생각을 해야 합니다.

소스코드

n = int(input())
arr = []
for _ in range(n):
  a, b = map(int, input().split())
  arr.append((a, b))
  
arr.sort(key = lambda x: (x[1], x[0]))

startTime = arr[0][0]
endTime = arr[0][1]
ans = 1

for i in range(1, n):
  if endTime <= arr[i][0]:
    endTime = arr[i][1]
    ans += 1

print(ans)

https://www.acmicpc.net/problem/2839

문제 해결을 위한 과정

이 문제는 dp를 이용하면 쉽게 해결할 수 있었습니다. 우선 dp 테이블을 만들고 최댓값으로 초기화해줍니다. 이후 해당하는 인덱스가 설탕으로 만들 수 있는 무게인지를 확인합니다. 이를 점화식으로 작성하면 다음과 같습니다.

dp [i] = min(dp[i], dp[i-설탕] + 1)

이를 소스코드로 작성하면 다음과 같습니다.

소스코드

bags = [3, 5]
n = int(input())
INF = int(1e9)
dp = [INF] * 5001
dp[0] = 0

for i in range(len(bags)):
  for j in range(5001):
    if j - bags[i] >= 0:
      dp[j] = min(dp[j], dp[j-bags[i]] + 1)

if dp[n] != INF:
  print(dp[n])
else:
  print(-1)