수학과의 개발자 도전기

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

문제 이해 

- 주어진 수들 중에서 세 개의 숫자를 구해 거기서 3 * (중위값 - 평균)의 최대값을 구한다. 

직관적으로 이해하기로는 중위값과 평균의 차이가 커야하므로 중위값은 최솟값과 비슷한 숫자여야하고 평균이 커야 하므로 배열의 최댓값이 무조건 들어가야 한다고 생각했다. 따라서 (0, 1, -1) 또는 (0, -2, -1) 두 개의 집단만 비교하면 된다고 생각해 진행했는데 21%에서 틀렸다. 

강의를 들어보니 중위값은 배열 전체의 값이 후보가 될 수 있고, 중위값을 기준으로 (중위값 - 최소 평균)과 (중위값 - 최대 평균) 중 최대값들을 누적해 가는 거라고 했다. 고려해야하는 케이스가 두 가지인 이유는 두 값의 절댓값을 계산하기 때문이다. 절댓값은 결국 두 값의 수직선 상에서의 거리이므로 중위값에서 최소의 값을 빼는 게 클 수도 또는 최대 평균에서 중위값을 빼는 게 클 수도 있다. 

풀이 로직

- 숫자들을 numbers에 저장한 뒤 오름차순 정렬한다.

- numbers의 원소들을 선형 탐색하면서 i번째 원소를 중위값으로 설정한 뒤 max_avg, min_avg를 구한다. 

- max_avg를 구하는 방법은 i번째 원소보다 작은 원소 중에 가장 큰 (i - 1) 원소와 배열 최대값인 (-1) 원소를 합해서 3으로 나누면 된다.

- min_avg를 구하는 방법은 i번째 원소보다 큰 원소중에 가장 작은 (i + 1) 원소와 배열 최소값인 (0) 원소를 합해서 3으로 나누면 된다.

- 각 중위값에서 최대값을 answer에 누적했다가 또 거기에서 최대값을 출력하면 정답이다. 

정답 풀이

import sys
input = sys.stdin.readline

n = int(input())

numbers = []
for _ in range(n):
    numbers.append(int(input()))

answer = []
numbers.sort()
for i in range(1, n - 1):
    median = numbers[i]
    max_avg = numbers[i - 1] + median + numbers[-1]
    min_avg = numbers[0] + median + numbers[i + 1]
    answer.append(max(abs(max_avg - 3 * median), abs(min_avg - 3 * median)))
    
print(max(answer))

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

- 정답 풀이 : 

예제3을 이해하자면 

k=4, result = [4,1]

(while) k=3, result = [4,7], k=2 result=[7]

k=2 result = [7,7]

k=2 result = [7,7,2]

k=1 result = [7,7,5]

k=1 result = [7,7,5,2]

k=0 result = [7,7,5,8]

k=0 result = [7,7,5,8,4,1]

25일 만에 그리디 50문제 2차 풀이 끝!!

N,K=map(int,input().split())
data=list(input())
result=[]
k=K

for i in range(N):

    #뺄 수 있는 횟수가 남아있고, 더 큰 숫자가 오른쪽에 있고, 아직 가장 큰 숫자가 오지 않았을 때
    while k>0 and result and result[-1]<data[i]:
    
        #result의 오른쪽 원소를 제거해야하므로
        result.pop()
        k-=1
        
    result.append(data[i])
    
print(''.join(result[:N-K]))

의아한건, 어차피 k==0이 될 때까지 루프를 돌리는데 마지막 result의 길이는 N-K인데 굳이 result[:N-K]로 설정해야하는 이유가 있나? 

하고 없이 돌려봤는데 75%에서 틀렸다. 어떤 경우 때문에 그런지 궁금하다,,,

해결

이 블로그를 참고하면 될 것 같다. 반례로 5 3, 43344가 있다. 이때 result=[4,4,4]가 나오는데 이때는 두자리 수만 출력해야하므로 44가 나오게 하려면 result[:N-K]를 해줘야한다 

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

-정답 풀이 :

1번부터 비행기의 게이트 번호 중 빈 게이트에 넣는 것이라 이해해서 완전 탐색을 생각했지만, 이건 당연히 시간초과가 날 것 같아서 

다른 풀이를 시도했으나, 5%에서 계속 틀려서 구글링을 했다. 

찾아보니 union-find라는 개념을 이용하는데, 아직 정확히 이해가 가지 않았다. 

같은 부모(루트)에 대해서 연결하는 것 같은데 이 부분은 좀 더 공부해야할 것 같다 

아무튼 정답풀이

코드 참고한 블로그

설명 참고한 블로그 

import sys
input=sys.stdin.readline

answer=0
g=int(input())
p=int(input())
planes=[]
parent=[i for i in range(g+1)]

for _ in range(p):
    planes.append(int(input()))

def find(x):
    if parent[x]==x:
        return x
    parent[x]=find(parent[x])
    return parent[x]

for plane in planes: #각 비행기의 게이트 번호
    docking=find(plane)
    if docking == 0: #도킹할 수 있는 게이트가 없는 경우
        break
    #해당 비행기와 게이트는 도킹했다는 것을 나타내기 위함
    parent[docking]=parent[docking-1]
    answer+=1
    
print(answer)

-삽질한 풀이;;

g=int(input())
p=int(input())
planes=[]
for _ in range(p):
    planes.append(int(input()))
planes=[0]+planes
visit=[0]*(g+1)
visit[0]=1
if g==1:
    print(1)
   
else:    
    i=1
    flag=False
    while True:
        if i==g:
            break
        for j in range(planes[i],-1,-1):
            if visit[j]==0:
                visit[j]=1
                flag=True
                break
        if not flag:
            break
        else:
            i+=1
       
    print(sum(visit)-1)

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

-정답풀이 :

도착지가 가까운 곳을 기준으로 박스를 싣는다. 

마을 중에서 택배양이 최소인 택배를 싣는 이유는 적게 싣고 빨리 배달해야 후에 더 많은 택배를 실을 수 있기 때문이다. 

택배를 실었을 때 남은 적재량을 저장한다

참고한 블로그 : https://javaiyagi.tistory.com/586

n,c=map(int,input().split())
m=int(input())
boxes=[]
arrive=[c]*n

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

answer=0
for i in range(len(boxes)):
    minNum=c+1
    #시작마을,도착마을
    a,b=boxes[i][0],boxes[i][1]    
    for j in range(a,b):
    	#지나가는 마을 중 최소 적재량 찾기
        minNum=min(minNum,arrive[j])
        
    #a마을에서 보낼 적재량과 a와 b사이에 있는 택배중 적은 적재량 비교??
    x=min(minNum, boxes[i][2])
    answer+=x
    for j in range(a,b):
        arrive[j]-=x
       
print(answer)

-시도해본 풀이 :

나름 풀어본다고 풀었는데, 계속 틀렸던 풀이다. 

n,c=map(int,input().split())
m=int(input())
boxes=[]
for _ in range(m):
    boxes.append(list(map(int,input().split())))
boxes.sort(key=lambda x : x[1])
arrive=[0]*(n+1)
before=[[] for _ in range(n+1)]
for i in range(m):
    x,y,z=boxes[i]
    before[x].append([y,z])
current=0
#처음 트럭에 택배 싣는 경우 
while True:
    if current == c:
        break
    x,y,z=boxes.pop(0)
    if current + z > c:
        arrive[y]=c-current
        current=c        
    else : 
        arrive[y]+=z
        current+=z
        
result=0
for i in range(1,n+1):
    if arrive[i]!=0:
        result+=arrive[i]
        arrive[i]=0
        #i번 마을에 보낼 택배가 있는지 확인
        if len(before[i])!=0:
            for j in range(len(before[i])):
                one,two=before[i][j]
                if sum(arrive)<c:                    
                    if sum(arrive)+two<=c:
                        arrive[one]+=two
                    else:
                        arrive[one]+=(c-sum(arrive))
                                       
print(result)