코딩하는 eroke

문제: 보물

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

크기 N의 배열 A, B이 있고, 위 공식 값이 최소가 되도록 A의 원소 위치를 변경하는 문제이다.

위 공식 값이 최소가 되려면 A[N-1] * B[N-1] 이 A의 최소값 * B의 최대값이 되어야 한다. 

나는 직접 원소를 이동시키진 않았고 A, B 배열을 복사해 최대값, 최소값을 갱신하고 삭제해가며 값을 계산했다.

풀이

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    tmpA = A
    tmpB = B
    answer = 0

    for i in range(N):
        mina = min(tmpA)
        maxb = max(tmpB)
        if len(tmpA)>0:
            tmpA.remove(mina)
            tmpB.remove(maxb)
        answer += (maxb * mina)

    print(answer)

요새 알고리즘을 하는둥 마는둥 깔짝이다

저번 주에 오오오오랜만에 코테를 무려 4개나 치루고,, 많은 자극을 받았다.

기본 문제부터 다시 차근차근 풀어볼 예정으로 오랜만에 백준으로 문풀을 했다.

문제 : 다리놓기

< 그림과 같이 강 동쪽(M)에서 강 서쪽(N)으로 겹치지 않게 다리를

놓을 수 있는 경우의 가지수를 출력하면 된다 ~_~

조합문제여서 python combinations를 사용해서 쓰면 (N=13, M=29)만 되어도

실행시간이 엄청 오래걸리고 제출 시 런타임에러가 발생한다.

문제에서 의도한 바는 조합 공식 (m!/n!(m-n)!) 을 활용해 푸는 거인 것 같지만,,

파이썬에는 조합의 개수를 바로 구해주는 math 함수가 있다. (개꿀)

풀이

import math

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N,M = map(int,input().split()) # mCn
        arr = list(range(1,M+1))

        #print(len(list(it.combinations(arr,N)))) #Runtime ERR
        print(math.comb(M,N))

math.comb(M,N)를 사용하면 M개에서 N개를 조합으로 선택할 때의 경우의 수를 출력한다.

문제 : 

오랜만에 그리디 문제도 풀어봤다.

그리디로 풀어야되는데 감잃고 고냥 조합으로 구하다가 메모리 초과로 실패 한번 띄우고 정렬해서 다시 풀었다.. (반성중)

그리디와 정렬은 뗄 수 없다는 사실!!! 잊지말자!!!!

풀이 1

N=int(input())
t=list(map(int,input().split()))
G=[]

for i in range(N):
    G.append((i+1,t[i]))
G.sort(key=lambda x: x[1])
#print(G)
tmp=res=0
for x,y in G:
    tmp+=y
    res+=tmp
print(res)

파이썬 sort()는 lamba를 이용해서 정렬 조건을 추가할 수 있다.

다중 조건일 때는 튜플을 이용하자  G.sort(key = lambda x : (x[0], -x[1]))

풀이 2

n=int(input())
p = list(map(int,input().split()))
p.sort()

res=[0]*n
res[0]=p[0]
for i in range(1,n):
    res[i] = res[i-1]+p[i]

print(sum(res))

나중에 보니 굳이 튜플로 풀지 않아도 되는 문제여서 다시 풀었다. (속도도 개선됨!)

문제 : 

Solution

import sys
from collections import deque
dq=deque()
op=deque()

N=int(input())
x=int(input())

for i in range(1,x+1):
    dq.append(i)
    op.append('+')

maxx=dq[-1]
dq.pop()
op.append('-')

for i in range(N-1):
    x=int(input())
    while x>maxx:
        maxx+=1
        dq.append(maxx)
        op.append('+')
    if len(dq)==0:
            print("NO")
            sys.exit(0)
    while x<dq[-1]:   
        dq.pop()
        op.append('-')    
    dq.pop()
    op.append('-')

for x in op:
    print(x)

자기 자신도 빼주는게 중요하당

1년 전 C++로 풀었을 땐 틀렸는데 올해 파이썬 시작하고 다시 풀어보니 맞았다,,8ㅅ8

꾸준히 공부하니 조금씩 성장하는게 느껴진다 무야호 ~

문제 :

한 달 전까지 못 풀던 문제를 다시 도전해보았다.

단순 위상정렬로만 접근해서는 틀린다고 나온다 ㅠㅠ 

건물들은 동시에 여러 개를 지을 수 있으므로 의존성 있는 건물 중 오래 걸리는 시간으로 갱신하며 계산되어야 한다..

Solution 1 : 2차원 배열

from collections import deque
N=int(input())
val=[0]*N

G=[[0]*N for _ in range(N)]
degree=[0]*N
dq=deque()

for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[i][tmp[j]-1]=1
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for i in range(N):
        if G[i][x]==1:
            degree[i]-=1
            res[i]=max(res[i],res[x]+val[i])
            if degree[i]==0:dq.append(i)        

for x in res:
    print(x)

res[i]=max(res[i],res[x]+val[i]) << 이 부분이 핵심이다

첫 번째 풀이는 2차원 배열에 연결성을 부여해 접근하였다.

파이썬의 defaultdict 을 이용하면 선행되어야 하는 건물에 의존적인 건물들을 추가하여 풀이할 수 있다.

개인적으로 첫 번째 풀이가 맘에 들지만 아래처럼 접근해야 하는 경우도 있을 것 같아 추가한다.

Solution 2 : defaultdict

from collections import deque, defaultdict
N=int(input())
val=[0]*N

G=defaultdict(list)
degree=[0]*N
dq=deque()


for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[tmp[j]-1].append(i)
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for y in G[x]:
        res[y]=max(res[y], res[x]+val[y])
        degree[y]-=1
        if degree[y]==0:
            dq.append(y)

for x in res:
    print(x)

이런식으로 선행되어야하는 건물: [의존건물들] 로 딕셔너리가 형성된다. 

(defaultdict는 딕셔너리를 리스트처럼 사용할 수 있게 해주는 라이브러리)

백준 수 찾기 에 이어 백분 이분탐색 카테고리의 문제를 풀려했는데

'수 찾기' 문제랑 너무 비슷해서 그냥 이것도 딕셔너리로 풀어버렸다..

문제 

Solution

#숫자카드 2
N=int(input())
A={}
a=map(int,input().split())

for x in a:
    if x not in A:
        A[x]=1
    else: A[x]+=1

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

for x in b:
    if x not in A: print(0,end=' ')
    else: print(A[x],end=' ')

다음은 진짜진짜 이분탐색으로 풀어야지...

이분탐색 연습 좀 하려고 간만에 백준 사이트에 들어갔다.

문제:

웬걸 연습하려는 이분탐색은 안쓰고 딕셔너리로 풀었다.. 

Solution

N=int(input())
A={}
a=map(int,input().split())

for x in a:
    if x not in A:
        A[x]=1

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

for x in b:
    if x not in A: print(0)
    else: print(1)

랜선자르기나 풀러 가야지,.