수학과의 개발자 도전기

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

-정답풀이: 

a,b=map(int,input().split())

ans=1
while True:
    if b==a:
        break
    elif (b%2 !=0 and b%10 !=1) or b<a:
        ans=-1
        break
    else:
        if b%2==0:
            b//=2
            ans+=1
        elif b%10==1:
            b=(b-1)//10
            ans+=1

print(ans)

-틀린풀이: 

• 시간초과가 났던 문제. 
• 그래서 -1이 출력되는 경우를 while문 초반에 넣으면 시간초과가 해결될 것이라고 생각했다. 
• 3번-9번 라인을 추가했다.
• a와 b가 같은 수 일때도 생각하고
• -1이 출력되는 경우를 생각해야하는데 b의 끝자리 수가 1이 아니고 b가 2의 배수가 되면 안되거나 b가 a보다 작은 경우 -1이 출력된다.

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

우선순위 큐를 이용한 문제. 

스스로 풀어보면서 특정 가방에 해당하는 특정 보석을 넣고 리스트에서 없애고 싶었는데 그 방법을 몰랐다. 

구글링 해보니 조건을 만족하는 원소를 없앨 때 heapq.pop()을 이용한다는 것을 배웠다. 

다음번에는 이 방법 적용해봐야겠다 

-정답 풀이: 

import heapq
n,k=map(int,input().split())
s=[]
l=[]
for _ in range(n):
    s.append(list(map(int,input().split())))
for _ in range(k):
    l.append(int(input()))
l.sort()
s.sort()

cnt=0
ans=[]
for i in l:
    while s and i >= s[0][0]:
        heapq.heappush(ans,-s[0][1])
        heapq.heappop(s)
    if ans:
        cnt+= heapq.heappop(ans)

print(-cnt)

문제 푸는 아이디어는 다음과 같다.

각 가방에 담을 수 있는 최대 가치의 보석을 담되 작은 가방부터 보석을 담는다.

것을 구현할 때 최대힙과 최소힙을 사용한다. 

가방들을 용량의 오름차순으로 정렬했을 때 

각 가방에 담을 수 있는 모든 보석을 찾을때 최소힙을 사용하고

각 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 찾을 때 최대힙을 사용한다. 

출처: https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-1202-%EB%B3%B4%EC%84%9D-%EB%8F%84%EB%91%91-Python

• 15번: 보석의 최소 무게보다 가방의 무게와 보석의 무게가 같거나 큰 경우에만 while문 수행
• 16번: ans 리스트에 해당 보석의 가격의 음수값을 넣는다.(Heap에서는 최솟값이 맨 첫번째이고, 문제에서 구하는 수는 최댓값이기 때문에 마이너스를 붙여서 값을 넣는다)
• 17번: 보석 리스트에서 뺀다. (?)-> 다른 블로그 찾아보니 있어도 되고, 없어도 되는 코드인 것 같다. 
• 조건을 만족하는 보석의 가격들을 하나씩 더한다
• 20번은 왜 있는지 잘 모르겠음(?)-> 20,21번을 빼고 코드 돌려도 똑같이 정답이 나온다. 

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

알고보니 엄청 쉬웠던 문제 

-정답풀이: 

n=input()
cnt=0

for i in range(len(n)-1):
	if n[i] != n[i+1]:
		cnt+=1  
print(cnt//2)

1의 묶음은 1로 생각하고, 0의 묶음은 0으로 생각하면 00011000은 010으로 봐도 무관하다. 길이에 관계없이 문자가 바뀌는지만 보면 되기 때문.

0과 1 은 0번 바꾸고, 길이가 1 -> 바뀌는 구간 0번이라 0번 바꾼다

10,01 은 1번 바꾸고, 길이가 2 -> 바뀌는 구간 1번, 1번 바꾼다 

010은 1번 바꾸고, 길이가 3 -> 바뀌는 구간 2번, 1번 바꾼다

0101은 2번 바꾸고, 길이가 4 -> 바뀌는 구간 3번, 2번 바꾼다

01010은 2번 바꾸고, 길이가 5 -> 바뀌는 구간 4번, 2번 바꾼다 

010101은 3번 바꾸고, 길이가 6 -> 바뀌는 구간 5번, 3번 바꾼다

0101010은 3번 바꾸고, 길이가 7  -> 바뀌는 구간 6번, 3번 바꾼다 

따라서 바뀌는 구간 수를 cnt라고 한다면, 바꾸는 최소 횟수는 (cnt+1)//2임을 알 수 있다. 

-다른 풀이

숫자가 0,1 밖에 없으므로 숫자가 바뀌는 지점을 기준으로 생각하면된다

해당위치에 있는 숫자가 0이면 모두 1로 바꾸는 경우(one)를 세고, 

숫자가 1일 때 모두 0으로 바꾸는 경우(zero)를 센다 

0이 1로 바뀌는 횟수와 1이 0으로 바뀌는 횟수 중 최솟값을 출력하면 정답이다

data=input()
zero=0 #전부 0으로 바뀌는 경우
one=0 #전부 1로 바뀌는 경우

if data[0]=='1':
	zero+=1
else:
	one+=1
    
for i in range(len(data)-1): #0부터 len(data)-2까지 반복문 돌림 -> 실제로는 1부터 len(data)-1까지 반복문 수행
	if data[i] != data[i+1]:
    	if data[i+1] =='1': #i번째가 '0'이었다는 의미
        	zero+=1
        else:
        	one+=1
print(min(zero,one))

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

-정답풀이:

def camp(l,p,v):
    ans=0
    s=0
    k=0
    s=v//p
    k=min(v%p,l)
    ans=(l*s)+k
    return ans
a=1

while(True):
    l,p,v=map(int,input().split())
    if l==0 and p==0 and v==0:
        break
    print("Case %d: %d" %(a,camp(l,p,v)))
    a+=1

-틀린풀이: 

• 6번,11-13번 라인을 잘 몰라서 틀렸던 문제.
• 이제 테스트케이스가 주어지지 않는 경우는 while(True): if~:break문을 사용하도록 하자
• 6번 같은 경우는 남아있는 캠핑일수와 원래 캠핑 이용하는 횟수를 비교해 최솟값을 넣어야한다