261. 뒤풀이
https://www.acmicpc.net/problem/14575
1) 어떤 전략(알고리즘)으로 해결?
- 이분탐색
2) 코딩 설명
<내 풀이>
import sys
n,t = map(int, sys.stdin.readline().strip().split())
people = []
llis = 0 ; rlis = 0
maxl = -1
maxr = -1
res = 10**10 #
for _ in range(n) :
l,r = map(int, sys.stdin.readline().strip().split())
people.append((l,r, r-l))
# r-1 은 내 최대주량 - 최소주량,
# 최대 주량이 커버쳐줄 수 있는 양, 즉 최소주량 마시고 남은 주량
llis+=l # 최소 주량 다 더했는데 t보다 큰 경우 불가능 체크용 !
rlis+=r # 최대 주량 다 더했는데 t보다 작은 경우 불가능 체크용 !
if maxl < l : maxl = l
if maxr < r : maxr = r
# 최소양들 다 더했는데 t보다 큰 경우
# 최대양들 다 더했는데 t보다 작은 경우
# => 불가능
if llis > t or rlis < t :
print(-1)
exit(0)
# 불가능 아닌 경우엔 이분 탐색
l,r = maxl, maxr
# 최소 주량들 중 max 인 아이 (최소 후보) 부터
# 최대 주량 중 max 인 아이 (최대 후보)
# 후보 범위
while l<=r :
mid = (l+r)//2
chk = t # 술 할당량
cover = 0 # 술 커버 가능 여부 측정
for p in people :
pl,pr, pcover = p[0], p[1], p[2]
# 최소 주량, 최대 주량, 최소 주량 마시고 더 마실 수 있는 양
# 전부 일단 최소 주량부터 마시게 해야함
chk-=pl # 할당량에서 최소주량 빼
# chk에는 모자란 수만 남음 (채워야하는 술할당량)
cover+= min(mid-p[0], p[2]) # 이 부분에서 비교가 필요 !!
# 지금 정해놓은 주량에서 최소 주량 뺀 것 vs 사용자의 최대 주량에서 최소주량 뺀 것
# 중 더 작은 범위
# ex : (정해놓은 주량이 7잔이고 최소 주량이 3잔) vs (최대 주량 8잔 최소 주량 3잔)
# 이 경우는 전자
# ex : (정해놓은 주량이 7잔이고 최소 주량이 3잔) vs (최대 주량 5잔 최소 주량 3잔)
# 이 경우는 후자
if cover >= chk : # 사람들이 더 마셔줄 수 있는 상황이면 mid 값 이하 ok
# 더 적은 mid 값으로도 사람들이 감당가능한 지 검사 위해서
# r 을 줄여줌
if res > mid :
res = mid
r=mid-1
else :
# 사람들이 감당할 수 없다면~
# 조금 더 주량을 늘려라~
l=mid+1
else : print(res)
< 내 틀렸던 풀이, 문제점>
4프로서 메모리 초과 !
import sys
sys.setrecursionlimit(10**5)
n,t = map(int, sys.stdin.readline().strip().split())
people = []
slis = [] # s후보들 담을 공간
for _ in range(n) :
l,r = map(int, sys.stdin.readline().strip().split())
주량 = []
for 주량후보 in range(l,r+1) :
주량.append(주량후보)
people.append(주량)
def dfs(seq,chklis) :
global slis
# print(seq,chklis )
for i in range(len(people[seq])) :
chklis.append(people[seq][i])
if len(chklis)==len(people) and sum(chklis)==t :
slis.append(max(chklis))
# print("slis ~ " , chklis, slis)
if seq+1<len(people) :
dfs(seq+1, chklis)
chklis.pop()
chk=[] # chk 에는 내가 마시기로 한 주량이 담긴다.
dfs(0,chk)
# print(slis)
# 만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력
# 문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력
if len(slis)==0 : # 만약 slis 에 도달한 애 없으면 끝
print(-1)
exit(0)
else :
print(min(slis))
4프로 메모리초과
from collections import deque
import sys
sys.setrecursionlimit(10**5)
n,t = map(int, sys.stdin.readline().strip().split())
people = []
slis = [] # s후보들 담을 공간
for _ in range(n) :
l,r = map(int, sys.stdin.readline().strip().split())
주량 = []
for 주량후보 in range(l,r+1) :
주량.append(주량후보)
people.append(주량)
def bfs(seq,chklis) :
q = deque()
q.append((seq,chklis))
while q :
# print(q)
nowseq , nowchklis = q.popleft()
for i in range(len(people[nowseq])) :
nowchklis.append(people[nowseq][i])
# print(nowchklis, nowseq, " ggg ")
if len(nowchklis)==len(people) and sum(nowchklis)==t :
# print("hi", nowchklis)
slis.append(max(nowchklis))
# print("slis ~ " , chklis, slis)
if nowseq+1<len(people) :
# print(nowchklis , " 이제 넣을게잉 ")
q.append((nowseq+1, nowchklis.copy()))
nowchklis.pop()
chk=[] # chk 에는 내가 마시기로 한 주량이 담긴다.
bfs(0,chk)
# print(slis)
# 만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력
# 문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력
if len(slis)==0 : # 만약 slis 에 도달한 애 없으면 끝
print(-1)
exit(0)
else :
print(min(slis))
이제 놀랍지 않은 메모리 초과 ^^
from collections import deque
import sys
n,t = map(int, sys.stdin.readline().strip().split())
people = [] ; s = 1000000001
for _ in range(n) :
l,r = map(int, sys.stdin.readline().strip().split())
people.append((l,r))
q = deque()
q.append((0,[],-1))
while q :
nowseq , nowchklis, maxdr = q.popleft()
for i in range(people[nowseq][0], people[nowseq][1]+1) :
nowchklis+=i
if nowseq==len(people)-1 and nowchklis==t :
if (max(nowchklis)) < s :
s = maxdr
if nowseq+1<len(people) :
q.append((nowseq+1, nowchklis.copy()))
nowchklis-=i
chk=[] # chk 에는 내가 마시기로 한 주량이 담긴다.
if s==1000000001 : # 만약 slis 에 도달한 애 없으면 끝
print(-1)
exit(0)
else : print(s)
윗 방식들은 모든 경우의 수들을 다 가지치기 하는거여서 그랬던가봉가
오 이분탐색이었다 이분 탐색으로 다시 접근하자!!
14프로에서 틀림
import sys
n,t = map(int, sys.stdin.readline().strip().split())
people = []
llis = 0 ; rlis = 0
maxl = -1 ; maxr = -1
res = 10000000000
for _ in range(n) :
l,r = map(int, sys.stdin.readline().strip().split())
people.append((l,r, r-l)) # r-1 은 내 최대주량 - 최소주량,
# 최대 주량이 커버쳐줄 수 있는 양
llis+=l
rlis+=r
if maxl < l : maxl = l
if maxr < r : maxr = r
l,r = maxl, maxr
while l<=r :
mid = (l+r)//2
chk = t
cover = 0
for p in people :
pl,pr, pcover = p[0], p[1], p[2]
chk-=pl
# chk에는 모자란 수만 남음 (부족한 술양)
cover+=p[2]
if cover >= chk :
if res > mid :
res = mid
r=mid-1
else :
l=mid+1
# 술이 커버해줄 수 있는 양보다 모자란 양이 더 많은 경우
# 최소양들 다 더했는데 t보다 큰 경우
# 최대양들 다 더했는데 t보다 작은 경우
# => 불가능
if llis > t or rlis < t :
print(-1)
exit(0)
else : print(res)
<반성 점>
- 메모리 초과의 늪 ㅠㅠ 흑흑,,,,,
