15651 N과 M(3)
N과 M(1) 문제와 매우 비슷한 문제였다. 애당초 N과 M 문제들 자체가 순열 조합 문제라서, 순열 조합 중복순열 중복조합으로 이해하고 접근하면 바로 풀 수 있었다.
이 문제는 순열과 똑같은 맥락에, 중복을 추가한 문제였기 때문에 순열 코드에서 중복을 제거하는 부분만 없애주면 중복을 추가해줄 수 있게 되고 그러면 중복순열을 구현할 수 있었다. 따라서 for문 안에 if i not in s부분을 지워주면 된다. 나머지 코드는 15649 N과 M(1) 문제의 코드와 동일하다.
n, m = list(map(int, input().split()))
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n + 1):
s.append(i)
dfs()
s.pop()
dfs()
15652 N과 M(4)
위 문제와 정확히 똑같은 맥락으로 풀면 되는 문제였고, 중복조합 문제였기 때문에 조합에서 중복을 제거하는 코드만 없애줌으로써 중복을 허용해 문제를 해결할 수 있었다.
n, m = list(map(int, input().split()))
s = []
def dfs(start):
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(start, n + 1):
s.append(i)
dfs(i)
s.pop()
dfs(1)
1654 랜선 자르기
parametric search라고도 소개된 이 문제는 binary search를 응용해 풀 수 있었다. 문제에서 얻어갈 수 있었던 개념은 target을 하나로 설정해놓지 않고 binary search를 돌린다는 점이었다. 나는 보통 binary search라고 하면 target을 정해놓고 그것이 들어있는지 아닌지를 logn으로 빠르게 찾는 알고리즘이라고만 생각해서, python에서 in이 O(n)이라 쓰기 어렵다고 판단될 때 우회적으로 사용하는 정도로만 binary search를 생각하고 있었다.
하지만 이 문제에서는 target이 while문을 돌때마다 달라졌고, 특정 조건이 만족될 때 break 되는 구조였다고 생각한다. 예를 들어 랜선의 최대 길이가 계산의 편의성을 위해 800이라고 가정한다면 1~800을 binary search로 탐색한다. mid의 초기값은 400이 되는데 이 mid 값을 랜선들과 비교해서 몇개의 랜선이 만들어질 수 있는지 계산하고, 그것이 우리가 구하려고 했던 개수와 동일한지 purpose와 비교해 검사한다. 이 검사가 실패했을 경우 즉 purpose와 부합하지 않는 경우, binary search를 다시 해야했기 때문에 cnt는 while문 내에서 매번 0으로 초기화해주어야 한다.
binary search이기 때문에 mid의 왼쪽값을 탐색하는지 오른쪽값을 탐색하는지 결정해주어야 하는데, 이것은 cnt와 purpose의 대소비교로 결정한다. 만약 cnt 즉 내가 만든 랜선의 개수가 목표치보다 많다면 너무 작게 잘라서 많이 만들어진것이므로 랜선의 길이를 좀 더 늘려주어야 한다. 그렇기 때문에 mid의 오른쪽값을 탐색해주어야하고, 이것은 start = mid + 1로 설정해주면 된다. else의 경우, 랜선의 개수가 너무 적은 것인데 이것은 반대로 랜선이 너무 길어서 개수가 적은것이므로 랜선의 길이를 줄여주면 된다. 따라서 end = mid - 1로 설정해주어 왼쪽을 탐한다.
이렇게 랜선의 개수를 purpose와 맞춰주고, 우리가 구하는 것은 개수가 아니라 랜선의 길이이므로 마지막으로 end를 출력해주면 랜선의 길이를 출력해줄 수 있다.
n, purpose = map(int, input().split())
lansun = [0] * n
for i in range(n):
lansun[i] = int(input())
start, end = 1, max(lansun)
#parametric search
# binary search가 target을 설정해놓고 존재여부를 찾는 느낌으로만 많이 썼는데
# 이 문제에서는 target이 미정인 상태에서 이분탐색을 쓴 것이 핵심이었다고 생각.
while start <= end:
mid = (start + end) // 2
cnt = 0
for i in range(n):
cnt += (lansun[i] // mid)
# 만약 잘라서 만들어진 랜선의 개수가 목표보다 많으면 길이가 짧은 거로 여러번 자른 것이므로
# 랜선의 길이가 길어져야함. 그래서 mid의 오른쪽을 탐색하도록 설정
if cnt >= purpose:
start = mid + 1
# 자른 개수 cnt가 목표 개수보다 적으면 랜선의 길이를 너무 길게 해서 자른 것이므로
# mid의 왼쪽을 찾아서 랜선 길이를 줄여줌
else:
end = mid - 1
print(end)
2805 나무 자르기
위 문제와 거의 동일한 맥락의 문제였다. 다만, 문제를 잘 읽어야하는 것이 절단기가 아래서부터가 아니라 위에서부터 자른다는 것이다. 즉, 20 15 10 17 길이인 나무들이 있을 때 15m 절단기로 자른다면 잘라지는 나무는 20 17만 잘라지게 되고 따라서 20-15와 17-15 만큼만 잘라서 가져갈 수 있다.
이 문제도 위 문제의 맥락과 마찬가지로 1~max(tree)를 탐색한다. max가 20이라면 1~20을 탐색하고 mid의 초기값은 10이다. 이때, 우리가 cnt 에 넣어줄 나무는 mid보다 큰 나무들만 가능하다. 왜냐하면 위에서부터 자르는 절단기의 특성상, 높이에 미치지 못한다면 절단하지 못하기 때문이다. 따라서 mid보다 큰 나무들만 일단 잘라보고, cnt에 넣어준다. 만약 이 값이 purpose보다 크다면 우리가 나무를 너무 많이 자른 것이므로 나무의 길이를 줄여주어야 한다. 따라서 start = mid + 1로 mid의 우측을 탐색해준다. 생각을 잘해주어야 하는 것이, 오른쪽을 탐색하는 것이 나무의 길이를 줄여주는 것이다. 절단기의 특성상 위에서부터 자른다고 생각하면 편하다. 그래서 절단기의 높이를 올려주는 것이 곧 나무를 조금 자르는 것과 같은 것이다.
그리고 else의 경우 나무의 길이를 늘려주어야 하기 때문에 end = mid - 1 로 왼쪽을 탐색해준다. 이렇게 해서 end와 start가 엇갈리는 지점에서 while문을 빠져나오게 되고 그것이 바로 우리가 찾는 절단기의 높이가 될 것이다.
import sys
input = sys.stdin.readline
n, purpose = map(int, input().split())
trees = list(map(int, input().split()))
start, end = 1, max(trees)
while start <= end:
mid = (start + end) // 2
cnt = 0
for i in trees:
if i > mid: # trees[i] - mid > 0인 경우에만 자를 수 있으므로
cnt += (i - mid)
if cnt >= purpose:
start = mid + 1
else:
end = mid - 1
print(end)
* 느낀점
parametric search 는 binary search 를 응용한 문제였는데 거의 유사한 방식이었다. 다만, target이 미정인 상태에서 binary search를 돌려서 target을 찾는 것이 핵심이었고 조금은 고정관념이었던 binary search의 target을 다시 생각하는 계기가 될 수 있었다.
