그렇게 어려운 문제는 아니었다. 첫 날부터 캠핑장을 사용한다고 하면 최대 캠핑장 사용 일수를 구할 수 있다.
구체적으로는 V일 중 P일의 사이클이 V//P번 완전하게 반복하므로 L*(V//P)일동안 캠핑장을 사용하고, 마지막 부분은 V%P와 L중 작은 값 만큼 캠핑장을 사용한다. 따라서 캠핑장 최대 사용일은 L*(V//P) + min(V%P, L)이다.
예제로 주어진 L=5, P=8, V=20일 경우를 살펴보면
V//P = 2이므로 P일의 사이클이 2번 반복되므로 16일까지 10번 캠핑장을 이용하고, V%P = 4, L=5이므로 마지막 4일동안 모두 캠핑장을 사용하므로 총 14일동안 캠핑장을 이용한다. 소스코드는 다음과 같다.
import sys
i = 0
while True:
L, P, V = map(int, sys.stdin.readline().rstrip().split())
if L == 0 and P == 0 and V == 0:
break
print('Case %d: %d' % (i+1, L*(V//P) + min(V%P, L)))
i += 1
처음에 나타난 최대 중량을 구하는 방법을 찾는데 시간이 조금 걸렸다. 로프가 버틸 수 있는 최대 중량은 (선택한 로프들의 버틸 수 있는 중량 중 최솟값) x (선택한 로프의 개수)이다. 따라서 예제를 살펴보면 로프가 2개가 있고, 버틸 수 있는 중량이 10, 15이다. 여기서 로프를 모두 사용할 필요는 없으므로 가능한 경우의 수는 2가지이다.
① 버틸 수 있는 중량이 15인 로프만 사용 ==> 버틸 수 있는 중량 = 15 x 1 = 15
② 버틸 수 있는 중량이 10인 로프만 사용 ==> 버틸 수 있는 중량 = 10 x 1 = 10
③ 두 개의 로프를 모두 사용 ==> 버틸 수 있는 중량 = 10 x 2 = 20
따라서 버틸 수 있는 최대 중량은 20이다.
이를 통해 생각한 문제풀이 방법은 다음과 같다.
① 중량들을 내림차순으로 정렬하고, 최대 중량을 첫 번째 원소의 값으로 초기화
② 다음 로프가 추가되었을 때의 중량이 최대 중량보다 크면 최대 중량을 갱신
import sys
N = int(sys.stdin.readline())
ropes = []
for _ in range(N):
rope = int(sys.stdin.readline())
ropes.append(rope)
ropes.sort(reverse=True)
weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
weight = rope * (i+1)
if weight > max_weight:
max_weight = weight
print(max_weight)
제출 후 다른 분들의 코드를 살펴보았는데 리스트 표현식, max()함수 등을 이용하여 소스코드를 간결하게 작성이 가능했다. 따라서 간결한 버전의 소스코드는 다음과 같다.
import sys
N = int(sys.stdin.readline())
ropes = [int(sys.stdin.readline()) for _ in range(N)]
ropes.sort(reverse=True)
weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
max_weight = max(max_weight, rope*(i+1))
print(max_weight)
9461번(파도반 수열)문제처럼 규칙을 구하는 dp문제는 접해본 적이 있지만 이렇게 최대/최소를 구하는 유형의 dp문제는 처음 풀어보았다.
주어진 예제를 통해 풀이 방법을 설명해보도록 하겠다.
맨 밑에 있는 값들을 (1) 맨 왼쪽에 있는 수 (2) 맨 오른쪽에 있는 수 (3) (1)와 (2)사이에 있는 수로 나눌 수 있다. 먼저 (1)의 경우는
으로 오른쪽 상단 한 곳을 통해서만 올 수 있기 때문에 처음 입력한 정수 삼각형 값을 저장하는 리스트를 triangle, 최댓값을 저장하는 리스트를 d라고 하면, d[i][j] = d[i-1][j] + triangle[i][j]이다.
(2)의 경우는
으로 왼쪽 상단 한 곳을 통해서만 올 수 있기 때문에 d[i][j] = d[i-1][j-1] + triangle[i][j]이다.
(3)의 경우에 해당하는 5, 2, 6중 5에 대해서만 살펴보면
으로, 왼쪽 상단과 오른쪽 상단 두 곳을 통해서 올 수 있기 때문에 두 곳 중 최댓값을 가지는 곳에서 현재값을 더해야 최댓값을 갖게 된다. 따라서 d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]이다.
따라서 소스코드는 다음과 같다(별로 추천하지 않음. 맨 밑에 있는 소스코드가 좋음) .
import sys
n = int(sys.stdin.readline())
triangle = []
d = []
for _ in range(n):
nums = list(map(int, sys.stdin.readline().rstrip().split()))
d.append([0 for _ in range(len(nums))])
triangle.append(nums)
d[0][0] = triangle[0][0]
for i in range(1, n):
for j in range(0, i+1):
if j == 0:
d[i][j] = d[i-1][j] + triangle[i][j]
elif j == i:
d[i][j] = d[i-1][j-1] + triangle[i][j]
else:
d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]
print(max(d[n-1]))
채점 후, 다른 분들의 소스코드를 살펴보니 내가 한 것처럼 입력한 정수 삼각형 값을 저장하는 triangle과 값에 해당하는 최댓값 d리스트를 각각 만들지 않고, 하나의 리스트를 통해서 계산을 하였다. d[i][j]가 계산될 때 재사용하는 값들은 이전 줄들의 값이기 때문에 하나의 리스트를 갱신하며 계산해는 것이 공간적으로도 더욱 효율적이고 소스코드도 더욱 간결하였다.
import sys
n = int(sys.stdin.readline())
triangle = []
for _ in range(n):
nums = list(map(int, sys.stdin.readline().rstrip().split()))
triangle.append(nums)
for i in range(1, n):
for j in range(0, i+1):
if j == 0:
triangle[i][j] = triangle[i-1][j] + triangle[i][j]
elif j == i:
triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
else:
triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]
print(max(triangle[n-1]))
dp문제인데, dp문제를 거의 풀어본 적이 없어서 쉽지 않았다. 파도반 수열의 값 P(1) ~ P(11)의 값이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12인데, 규칙을 찾으려 노력했지만 처음에는 잘 보이지 않았다. 여러가지 관찰을 하던 중 홀수 번째와 짝수 번째 파도반 수열로 나누어서 살펴보았다.
짝수 번째 값들을 살펴보면 P(4) = P(1) + P(2), P(6) = P(3) + P(4), ..., P(n) = p(n-3) + p(n-2)이고, 홀수 번째 값들을 살펴보면 P(5) = P(2) + P(3), P(7) = P(4) + P(5), ..., P(n) = p(n-3) + p(n-2)이다. 따라서 n의 값이 홀수 짝수와 관계없이 P(n) = P(n-3) + P(n-2)이다.
사실 이러한 규칙은 홀수 짝수 나누지 않고도 발견할 수 있지만 나누지 않았을 때는 찾지 못하였다.
이에 맞춰서 작성한 소스코드는 다음과 같다.
import sys
def padovan(d, n):
if 1 <= n <= 3:
return 1
if d[n] != 0:
return d[n]
d[n] = padovan(d, n-3) + padovan(d, n-2)
return d[n]
T = int(sys.stdin.readline())
d = [0 for _ in range(101)]
d[1], d[2], d[3] = 1, 1, 1
for _ in range(T):
N = int(sys.stdin.readline())
print(padovan(d, N))
연산자로는 -와 +밖에 없기 때문에 덧셈을 먼저 계산한 후 뺄셈을 계산하면 최대한 큰 수를 빼게되어서 최솟값이 나올 것이라 생각하였다.
import sys
ops = sys.stdin.readline().rstrip().split('-')
for i in range(len(ops)):
if '+' in ops[i]:
nums = list(map(int, ops[i].split('+')))
sum = 0
for num in nums:
sum += num
ops[i] = sum
else:
ops[i] = int(ops[i])
result = ops[0]
for i in range(1, len(ops)):
result -= ops[i]
print(result)
import sys
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (high+low)//2
if arr[mid] < target:
low = mid + 1
elif arr[mid] == target:
return mid
elif arr[mid] > target:
high = mid - 1
return -1
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split(' ')))
arr.sort()
M = int(sys.stdin.readline())
targets = list(map(int, sys.stdin.readline().rstrip().split(' ')))
for target in targets:
if binary_search(arr, target) == -1:
print('0')
else:
print('1')
제출 후에 다른 분들의 코드를 살펴보니 수행시간이 유독 짧은 코드들이 있었는데, 이진 탐색이 아니라 set을 이용한 풀이가 있었다. set을 이용한 코드는 다음과 같다.
import sys
N = int(sys.stdin.readline())
arr = set(sys.stdin.readline().split())
M = int(sys.stdin.readline())
targets = sys.stdin.readline().split()
for target in targets:
if target in arr:
print('1')
else:
print('0')
