수학과의 개발자 도전기

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

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

문제 조건을 잘못 이해해서 예제2번에서 애를 좀 먹었다 

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)

위 조건을 x != y를 보고 카드에 적힌 숫자가 다른 거라고 생각했는데 그게 아니라

x와 y는 카드 번호이므로, 같은 카드를 뽑아서 더하면 안 된다는 것이지, 카드의 값이 꼭 달라야할 필요는 없는 것이다 

그래서 우선순위 큐에서 가장 왼쪽 두 숫자의 합을 계속 추가해 나가면 답이 나온다 . 

-> 문제를 좀 더 꼼꼼히 읽자!!!

-정답풀이 

import heapq
n,m=map(int,input().split())
data=list(map(int,input().split()))
data.sort()

for i in range(m):
    a=heapq.heappop(data)
    b=heapq.heappop(data)
    c=a+b
    heapq.heappush(data,c)
    heapq.heappush(data,c)
print(sum(data))

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

-정답풀이: 

시작과 끝 통나무도 연결되어있으니까 이 둘의 차이도 최소가 되어야 한다고 생각해 주어진 값을 오름차순으로 정렬한 다음 

0번 인덱스는 0번에, 1번 인덱스는 n-1에 넣으면 될 것 같다고 생각했다. 

정렬한 상태에서 왼쪽 두개를 꺼내면 되므로, data.pop을 사용했다. 

n이 짝수면 n//2개로 충분한데, n이 홀수면 data안에 원소 하나가 남으므로 그거는 중심에 넣어준다 

위와 같은 과정으로 만든 result 리스트 각 원소의 차이 중 최댓값을 출력하면된다. 

0과 n-1인덱스 값의 차이는 이미 최소이므로 비교하지 않아도 된다 

t=int(input())

for _ in range(t):
    n=int(input())
    data=list(map(int,input().split()))
    result=[0]*n
    data.sort()
    for i in range(n//2):
        a=data.pop(0)
        b=data.pop(0)
        result[i]=a
        result[n-1-i]=b
    if len(data):
        result[n//2]=data.pop(0)
    answer=0
    for i in range(1,n):
        answer=max(answer,abs(result[i]-result[i-1]))
    print(answer)

-2022.02 풀이 

증가하는 부분 수열, 감소하는 부분수열을 합친 문제다 

t=int(input())

for _ in range(t):
    n=int(input())
    s=sorted(list(map(int,input().split())))
    odd=[]
    even=[]
    for i in range(n):
        if i%2 ==0:
            even.append(s[i])
    for i in range(n-1,-1,-1):
        if i%2==1:
            odd.append(s[i])    
    result=even+odd
    ans=0
    for i in range(1,n):
        ans=max(ans,abs(result[i]-result[i-1]))
    print(ans)

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

-정답풀이:

예제를 보니까 뭔가 규칙성이 있어서 탐색 스타일은 아닐 것 같다고 여겼다. 

그리고 지나온 칸 수를 세는 건줄 알았는데, 그게 아니라 주어진 방법대로 움직이고, 멈춘 칸의 갯수를 세는 것이었다.

그걸 기준으로 세보니까 세로 최소 3, 가로 최소 7은 되어야 주어진 방법을 모두 사용할 수 있었고, 

이보다 작은 수들로는 그냥 가능한걸로 아무거나 움직이면 된다. 

이 경우에 따라 모두 나눠야 하기 때문에 어려웠던 것 같다. 

n==3이 기준이니까 이보다 작은 1,2인 상황에 대해서도 작성하면 된다 

n==2일 때 min(4,(m+1)//2)가 이해가지 않았는데, 

2x1일 때는 1, 2x2일 때는 1, 2x3일 때는 2, 2x4일 때는 4, m>=4이상이면 움직일 수 없다(4칸은 지나쳐왔기때문에 이전과는 다른 방법으로 진행해야하는데, 세로 칸 수 때문에 할 수 없다)는 것을 써보니까 이해가 됐다

n>=3일 때, 가로가 6이하면 1,2,3,4 순서로 진행되고, m이 5,6일 때는 4보다 더 움직일 수 없다

m-2는 왜 하는 걸까??

n,m=map(int,input().split())

if n == 1:
    print(1)
elif n == 2:
    print(min(4,(m+1)//2))
else: #n>=3
    if m<=6:
        print(min(4,m))
    else:
        print(m-2)

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

인덱스 0부터 시작해서 순차적으로 비교해가는 방법을 생각했는데, 이렇게 하면 5,5,5 같은 경우에는 4,4,5로 의도와 다른 결과가 나온다. 

그래서 n-1부터 왼쪽으로 가면서 비교해야겠다고 생각했다. 

for j 문에서 range(n-1,i-1,-1)로 처음에 했는데 틀렸다가 i-1을 i로 바꾸니까 정답이 떴다 

-정답 풀이: 

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