방구석프로의 이야기

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)

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있는 문제였습니다. 이동할 수 있는 경우는 오른쪽, 아래 2가지 경우만 존재하므로 원본 배열과 같은 크기의 visited 배열을 만듭니다. 이후의 과정은 다음과 같습니다.

1. visited 배열을 조회함(0행 0열부터 n-1행 n-1열 까지)

2. 해당 칸이 직전 과정에서 이동한 칸이면(visited[i][j] != 0 이면) 위 또는 아래로 원본 배열에 해당하는 칸만큼 움직이기 단, 원본 배열의 해당 칸은 0이 아님

이 과정을 반복하면서 마지막에 도착했을 때 출력하면 됩니다.

소스코드

n = int(input())
dx = [0, 1]
dy = [1, 0]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
visited = [[0] * n for _ in range(n)]
visited[0][0] = 1

for i in range(n):
  for j in range(n):
    if graph[i][j] != 0 and visited[i] != 0:
      for k in range(2):
        nx = i + dx[k]*graph[i][j]
        ny = j + dy[k]*graph[i][j]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        visited[nx][ny] += visited[i][j]
print(visited[n-1][n-1])