수학과의 개발자 도전기

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

풀이 안보고 스스로 푼 문제(이게 얼마만인지)

예제2를 보고 i번째 인덱스의 값이 i+1번째 인덱스의 값보다 큰 경우만 계산하면 될 것 같다고 생각했다. 

그래서 if s[i]>s[i+1] 를 생각했고

s[i]는 s[i+1]보다 1만큼 작으면 된다

s[i]를 s[i+1]-1로 만들 때 감소한 만큼을 cnt에 저장한다 

-풀이:

그런데 위 코드가 예제1번에서는 적용되지 않았다. 

이유를 찾아보니 해당 풀이로 하면 [5,5,5]는 [4,4,5]가 되고 cnt는 2가 되어 정답이 아니다.

그래서 다른 방법을 생각해 보니 인덱스를 n-1부터 시작하면 어떨까 생각했다. 그러면 배열의 값이 모두 같아도 순차대로 나열할 수 있을 것이라 생각이 들었다. 그래서 다음과 같이 작성하고 코드 돌리니 정답이었다. 

-정답풀이: 

n=int(input())
s=[]
cnt=0
for _ in range(n):
    s.append(int(input()))  
for i in range(n-1,0,-1):
    if s[i] <= s[i-1]:
        cnt+=(s[i-1]-s[i])+1
        s[i-1]=s[i]-1
            
print(cnt)

-문제: 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)