pmcc(poly math coding competition) div.2 풀이

1. 암호 만들기(Password)

이 문제는 A와 B에서 공통인 부분 문자열이 P만 있는 B를 구하는 것이다.

근데 밑에 있는 코드처럼 할 필요 없이 그냥 b(P)만 출력해도 된다. B에 P만 있으면 되기 때문에 그냥 P만 출력해도 된다.

 

import sys
input=sys.stdin.readline
a=input().strip()
b=input().strip()
t=[0]*10
for i in range(len(a)):
    t[int(a[i])]=1
s=""
#print(t)
for i in range(1,10):
    if t[i]==0:
        print(str(i)+b)
        sys.exit()
print(b)

2. 마법의 돌 장난감(Stone)

이문제는 백준에 있는 두 번 뒤집기(2505)랑 세 번 뒤집기(2561) 같은 문제인데 대신 개수가 Q개이고 이 개수가 꼭 최소가 아니어도 된다 하지만 Q가 만약 100개를 넘어간다면 -1을 출력해야 된다. 이 문제는 예전에 올렸던 두 번 뒤집기(2505)와 거의 동일한 문제인데 두 번 뒤집기 코드에서 if nm <=2이 제한을 없애주고 if nm>100을 추가해서 따로 처리만 해주면 끝이다.

joseph0528.tistory.com/13

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))
u=[l[i] for i in range(a)]
t=[]
r=[]
o=0
im=a-1
def f(val,st,en):
    p=en-st+1
    for i in range((1+p)//2):
        val[st+i],val[en-i]=val[en-i],val[st+i]
def cn(val):
    nm=len(val)
    if nm>100:print(-1);sys.exit()
    print(nm)
    for i in range(nm):print(val[i][0],val[i][1])
    sys.exit()
for i in range(a):
    if l[i]!=i+1:
        for g in range(i+1,a):
            if i+1==l[g]:o=g;break
        t.append([i+1,o+1])
        f(l,i,o)
    if u[im]!=im+1:
        for g in range(im-1,-1,-1):
            if im+1==u[g]:o=g;break
        r.append([o+1,im+1])
        f(u,o,im)
    im-=1
if len(t)<len(r):
    cn(t)
else:
    cn(r)
#cn(t)
#cn(r)
#print(t,r)

3. 빛의 돌 옮기기(Light)

이 문제는 dp인데 dp를 잘 못하다 보니 생각보다 애를 먹었다.

점화식은 간단하다.

현재 선택되어 있는 줄과 같은 줄의 값을 더했을 때와 현재 선택되어있는 줄과 다른 줄의 값에 k를 더한 값 중 더 작은 값을 윗줄과 아랫줄에 저장하면 된다.

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
a,b=map(int,input().split())
l=[[0]+list(map(int,input().split())) for i in range(2)]
dp=[[0 for i in range(a+2)]for g in range(3)]
for i in range(a,0,-1):
    dp[1][i]=min([l[1][i]+dp[1][i+1],l[1][i]+dp[0][i+1]+b])
    dp[0][i]=min([l[0][i]+dp[0][i+1],l[0][i]+dp[1][i+1]+b])
s=min(l[0][0]+dp[0][1],l[0][0]+dp[1][1])
print(s)

 

4. 우물 파기(Water)

못 풀었다

 

5. 불꽃놀이(Fire)

일단 양끝을 동일하게 만드고 나머지 개수의 몫만큼 빼 주면 정답이다.

a=int(input())
l=list(map(int,input().split()))
s=max(l[0],l[a-1])-min(l[0],l[a-1])
if l[0]==l[a-1]:
    print(l[0]-(a-1)//2)
elif a-2>=s:
    print(min(l[0],l[a-1])-(a-1-s)//2)
else:
    print(max(l[0],l[a-1])-a+2)

 

6번은 문제를 잘못 읽어서 4시간 동안 삽질했다ㅜㅜ 7,8번은 보지도 못했다. 8문제 중 4솔이지만 dp를 풀어서 기분이 좋다.