수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/11000

회의실 배정과 비슷한 문제라고 생각했는데 이거는 하나의 강의실에 넣을 수 있는 최대 회의 개수이지만

이번 문제는 강의 수는 n개이고, 사용하는 강의실 개수를 최소로 하는 거라서 조금 다르다. 

-정답풀이(Pypy3으로 해야 시간초과가 발생하지 않는다): 

last 배열에 given의 첫번째 값을 넣고, 나머지 given값과 비교한다

강의실을 공유하는 경우는 else문으로 원래 있던 값을 heappop하고, 새로운 값을 heappush해준다(강의실 갯수 유지)

강의실을 공유하지 않는 경우는 if문으로 새로운 값을 heappush를 하면 된다

-틀린 풀이: 

뭔가 heapq를 이용해야할 것 같아서 import 해봤는데 아직 쓸 줄을 몰랐다,,, 

아 요새 그리디 문제 너무 안풀려서 스트레스 받는다,,, 

여기서 조건을 만족하는 걸 given에서 없애는 거라고 생각했는데, 따로 배열을 만들어서(last) 거기다가 heappush를 하는 방식

-문제: https://www.acmicpc.net/problem/1783

-정답풀이: 

세로 길이가 1이라면 어느 이동방법도 쓸 수가 없어서 1(시작지점,왼쪽 맨 아래)을 출력해준다

세로 길이가 2라면 2번,3번 방법만 쓸 수 있다. 모든 이동 방법을 쓰는게 아니므로 4와 (가로+1)//2의 값 중 작은걸 출력해준다 

세로 길이가 3 이상일때, 

가로가 6이하라면 모든 방법을 쓸 수가 없다. 1번과 4번만을 이용하는 게 최댓값이므로 4와 m의 값 중 작은 것을 출력해준다

가로가 7이상이라면 모든 방법을 쓸 수 있고, 알맞는 값을 출력해준다(m-2)

왜 (m+1)//2이고, m이고,m-2인지 모르겠네,,, 

n,m=map(int,input().split())
if n==1: #세로 길이 1일 때
    print(1)
elif n==2: #세로 길이 2일 때
    print(min(4,(m+1)//2))
else: #세로 길이 3이상일 때
    if m<=6: #가로가 6이하일때
        print(min(4,m))
    else:
        print(m-2)

-문제: https://www.acmicpc.net/problem/1543

문자열 비교는 처음 해본 문제다. 

해당 풀이 참고해서 비슷한 유형에서 이용해야할 것 같다

체감상 dp보다 그리디가 더 어려운 느낌

-정답풀이:

f=input()
s=input()
len1=len(f)
len2=len(s)
cnt=0
n=0
while n<= len1-len2:
    if f[n:n+len2]==s:
        cnt+=1
        n+=len2
    else:
        n+=1
           
print(cnt)

-문제: https://www.acmicpc.net/problem/1449

-정답풀이: 

시작지점과 그 시작지점에 테이프 길이를 더하면 그 사이의 위치에는 모두 막을 수 있다는 원리다 

n,l=map(int,input().split())
s=sorted(list(map(int,input().split())))
k=l
cnt=1
start=s[0]
end=s[0]+l
for i in range(n):
    if start <= s[i]<end:
        continue
    else:
        start=s[i]
        end=s[i]+l
        cnt+=1
print(cnt)

-틀린풀이:

i번째 위치랑 i+1번째 위치를 비교해서 테이프 길이보다 짧으면 테이프의 길이를 차이+0.5 만큼 줄이고, 아닌 경우는 갯수를 세는 식으로 생각했는데 11% 돌아가다가 틀렸다 

문제가 무엇인지 생각해봐야할 것 같다