수학과의 개발자 도전기

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

총 구매 가격이 최소가 되는 것이 목표이므로 굳기 같은 브랜드별로 구매하지 않아도 된다.

6개 패키지 값이 제일 싼 브랜드와 낱개 값이 가장 싼 브랜드만 생각하면 된다

그래서 주어진 행렬에서 0열과 1열 0행에 가장 작은 값만 오면 된다(sort 두번 하면 됨)

그리고 모든 경우 다 계산해서 리스트에 넣고 가장 작은 값을 구하면 되는 줄 알았는데 그게 아니라 

경우에 따라서 나오는 최솟값이 다르므로 경우 설정을 해야 정답을 구할 수 있다는 것을 알았다. 

-정답풀이 1: 

n,k=map(int,input().split())
s=[]
for _ in range(k):
    s.append(list(map(int,input().split())))
six_list=sorted(s,key=lambda a: a[0])
one_list=sorted(s,key=lambda a: a[1])
a=n//6
b=n%6
ans=0
if six_list[0][0] <= one_list[0][1]*6:
    ans=(a)*six_list[0][0]+b*one_list[0][1]
    if six_list[0][0] < one_list[0][1]*(b):
        ans= (a+1)*six_list[0][0]
else:
    ans=n*(one_list[0][1])
print(ans)

1패키지의 값이 낱개 6개의 값보다 같거나 작은경우에는 주어진 갯수에 맞게 구매하는 것이 최소이고

1패키지의 값이 낱개 6개의 값보다 작은 경우에는 원래 개수를 초과하게 패키지를 구매하면 된다.

패키지의 가격이 6개의 값보다 큰 경우에는 모두 낱개로 구매한다 .

-정답풀이 2: 

내가 푼 풀이

0열 기준으로 정렬한 리스트와 1열 기준으로 정렬하는 리스트 각각 다른 리스트에 저장한다 

n,k=map(int,input().split())
s=[]
ans=[]
for _ in range(k):
    s.append(list(map(int,input().split())))
six_list=sorted(s,key=lambda a: a[0])
one_list=sorted(s,key=lambda a: a[1])
a=n//6
b=n%6
for i in range(k):
    ans.append((a+1)*six_list[i][0])
    ans.append((a*six_list[i][0]+b*one_list[i][1]))
    ans.append(n*one_list[i][1])
print(min(ans))

-틀린풀이:

60%까지 진행되다가 틀렸다

경우를 나누지 않아서 틀린 줄 알았는데, 알고보니 0열 기준으로 정렬하는 거랑 1열 기준으로 정렬하는 거 모두 다른 행렬로 만들어야했다. 

정답풀이 2를 참고하면 된다

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