수학과의 개발자 도전기

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

그렇게 어렵지 않았던 문제다. 

처음에는 한 브랜드 당 패키지로만 살 때, 패키지+낱개, 낱개로만 살 때 중 최솟값을 출력하면 된다고 생각했는데

예제를 보니까 브랜드가 섞여도 상관없다는 것을 알게 된 뒤 

패키지에서 최솟값과 낱개에서 최솟값을 가지고 

min(패키지로만, 패키지 + 낱개, 낱개만)의 값을 출력했다 

Silver Level4 문제 

-정답풀이: 

n, m = map(int, input().split())
data=[]
for _ in range(m):
    data.append(list(map(int,input().split())))
    
data.sort(key=lambda x : x[0])
a=data[0][0]
data.sort(key=lambda x : x[1])
b=data[0][1]

answer=min(((n//6)+1)*a, (n//6)*a + (n%6)*b, b*n)
print(answer)

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

-정답풀이:

a에서 b로 푸는 게 아니라, b에서 a로 풀어야하는 문제. 

2로 나뉘는 수와 나뉘지 않는 수로 경우를 나눴는데, 47퍼센트까지가서 계속 틀리는 거다. 

그래서 이전에 풀었던 풀이를 참고하니 끝자리 수가 2의 배수나 1이 아닌 3,5,7,9는 연산을 실행할 수 없으므로 

거기서 멈춰줘야 한다. 그래서 이 부분을 추가하니 정답이 떴다 

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

count=0
while b>a:
    if b%2==0:
        b=b//2
        count+=1
    elif b%10 == 1:
        b-=1
        b=b//10
        count+=1
    else: #끝자리수가 3,5,7,9인 경우
        break
if b==a:
    print(count+1)
else:
    print(-1)

-47%에서 틀린 풀이 

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

count=0
while b>a:
    if b%2==0:
        b=b//2
        count+=1
    else:
        b-=1
        b=b//10
        count+=1
if b==a:
    print(count+1)
else:
    print(-1)

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

-정답풀이: 

import heapq

n,k = map(int,input().split())
jewel,bag = [], []
for _ in range(n):
    jewel.append(list(map(int,input().split())))
    
for _ in range(k):
    bag.append(int(input()))
    
jewel.sort()
bag.sort()

count=0
answer=[]
for i in bag:
    #하나의 가방에 담을 수 있는 보석 후보 모두 저장
    while jewel and i >= jewel[0][0]:
        heapq.heappush(answer,-jewel[0][1])
        heapq.heappop(jewel)
    #보석 후보가 있다면 그 중에서 가장 작은 가격(-최대가격)을 넣는다 
    if answer:
        count+=heapq.heappop(answer)
print(-count)

-시간초과 풀이 

for문에 while 넣는 구조는 동일한데(?) 안에 내용이 틀린 것 같다. 

일단 주어진 가방은 다 쓰는게 가장 많이 보석을 담을 수 있으니까 for문으로 전체 가방에 대해 탐색하고

while로 해당 가방에 담길 수 있는 보석을 선별하는 과정을 거친다(보석의 무게가 가방 수용 무게보다 작거나 같은 경우)

거친 보석들 중에서 가치가 가장 큰 것을 추가해 나가면 된다(여기서 -jewel[0][1], -count)가 나왔다 

import heapq

n,k = map(int,input().split())
jewel,bag = [], []
for _ in range(n):
    m,v=map(int,input().split())
    jewel.append([m,v])
    
for _ in range(k):
    bag.append(int(input()))
    
jewel.sort(key=lambda x: x[1])
bag.sort()

heapq.heapify(jewel)
answer=0
for i in range(k):
    while(True):
        m,v=heapq.heappop(jewel)
        if m <= bag[i]:
            answer+=v
            break
        else: 
            heapq.heappush(jewel,[m,v])
print(answer)

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

-정답풀이 :

숫자가 0,1 밖에 없으므로 0에서 1로(one), 1에서 0으로(zero) 바뀌는 지점만 세면된다고 생각했다. 

예제를 위 논리로 구해보니까 웬만해선 one과 zero가 같은 거다. 

다른 경우는 000001과 같이 하나만 바꾸면되는 경우. 이럴 때는 one == 1 이지만, zero ==0 이다. 그래서 

이 경우를 제외한 모든 경우는 one과 zero가 같다고 생각해서 마지막에 max로 출력했다. 

틀릴 줄 알았는데 금방 맞혔던 문제다 

data=list(input())
n=len(data)
zero,one= 0,0

for i in range(1,n):
    if data[i-1]=='0' and data[i]=='1':
        one+=1
    if data[i-1]=='1' and data[i]=='0':
        zero+=1
        
print(max(zero,one))

-다른 풀이

이 풀이는 나동빈 코테 책에서 공부했던 거다. 

숫자가 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))