#1932 정수 삼각형
🔗https://www.acmicpc.net/problem/1932
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
생각
DP 란거를 보고 점화식을 세워야겠다... 하고 머리를 굴려봤는데 도저히 감이 오질 안왔다.
그래서 직접 과정을 쓰면서 풀어보니 바로 규칙이 보였다. 하하하 앞으로는 일단 모르겠으면 한번 풀어보는게 나을듯!!
n번째 줄 i번째 dp 값은 n-1번째 줄 i-1번째 dp값과 i번째 dp값 중 큰 값을 선택해서 자기자신 노드와 더하면 된다. (양쪽 모서리 제외!)
점화식으로 작성해 보자면
왼쪽 모서리 (단, n>0)
dp[n][0]=dp[n-1][0]+tri[n][0]
오른쪽 모서리 (단, n>0)
dp[n][n]=dp[n-1][n-1]+tri[n][n]
그 외 (단, n>0)
dp[n][i]=max(dp[n-1][i-1],dp[n-1][i])+tri[n][i]
이를 코드로 구현하면 된다.
코드
import sys
n=int(sys.stdin.readline().rstrip())
dp=[]
for i in range(n):
tmp=list(map(int,sys.stdin.readline().split()))
dp.append(tmp)
for i in range(1,n): #dp
for j in range(i+1):
if j==0:
dp[i][j]=dp[i-1][j]+dp[i][j]
elif j==i:
dp[i][j]=dp[i-1][j-1]+dp[i][j]
else:
dp[i][j]=max(dp[i-1][j-1], dp[i-1][j])+dp[i][j]
print(max(dp[n-1]))#14501 퇴사
🔗https://www.acmicpc.net/problem/14501
문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
| 1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
|---|---|---|---|---|---|---|---|
| Ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| Pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
생각
왜이렇게 기시감이...
분명 풀었던 문제인 것 같은데??
1. 우선 save 리스트를 선언해서, 해당 날짜에 완료되는 상담을 (상담이 시작된날짜, 비용) 형태로 저장해놓자.
2. dp[n]=max(dp[해당 날짜에 완료되는 상담이 시작된 날짜]+비용) 점화식을 토대로 dp를 업데이트 시켜주자.
말로 풀어쓰기가 어려운데... 위의 예시를 토대로 dp를 업데이트 시키면
dp[0]=0
dp[1]=0
dp[2]=0
dp[3]=0
dp[4]=10 #max(dp[1]+10,dp[3]+10)
dp[5]=30 #dp[4]+20
dp[6]=45 #max(dp[2]+20, dp[5]+15)
dp[7]=45이런식!
코드
import sys
n=int(sys.stdin.readline().rstrip())
#0:T(기간) 1:P(금액)
table=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp=[0 for _ in range(n+1)]
save=[[] for _ in range(n+1)]
maxnum=0
for i in range(n):
if (i+table[i][0])<n+1:
save[i+table[i][0]].append((i,table[i][1]))
for i in range(n+1):
if save[i]:
for j in range(len(save[i])):
if maxnum<dp[save[i][j][0]]+save[i][j][1]:
maxnum=dp[save[i][j][0]]+save[i][j][1]
dp[i]=maxnum
else:
dp[i]=maxnum
print(max(dp))#18353 병사 배치하기
🔗https://www.acmicpc.net/problem/18353
문제
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.
예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.
이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.
병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.
생각
직접 풀어봤는데 규칙을 잘 발견하지 못하겠어서, 해설을 참고했더니 "가장 긴 증가하는 부분 수열"의 활용버전이였다.
이걸 보고 예전에 풀었던게 기억이 나가지고 풀어보았다.
점화식은
0≤j<i D[i]=max(D[i], D[j]+1) if array[j]>array[i]
코드
import sys
n=int(sys.stdin.readline().rstrip())
soldier=list(map(int,sys.stdin.readline().split()))
dp=[1 for _ in range(n)]
for i in range(n):
for j in range(i):
if soldier[j]>soldier[i]:
dp[i]=max(dp[i] , dp[j]+1)
print(n - max(dp))#2887 행성 터널
🔗https://www.acmicpc.net/problem/2887
문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
생각
그래프, 모든 노드를 최소한의 비용으로 연결하고자 한다. => 크루스칼!
그치만 모든 간선에 대한 가중치를 업데이트 시켜줄 수 없다. N이 최대 100,000 이기에..
어떻게 해야 모든 간선에 대한 탐색 없이 구현할 수 있을까?
두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. < 이 부분이 핵심인 것 같다!
x,y,z의 각 위치를 오름차순으로 정렬하고,
인접된 노드를 뺌으로써 가장 거리가 짧은 노드들만 간선 리스트에 들어갈 수 있도록 하자.
처음엔 내가 계속 좌표가 삼차원이다 보니, 문제도 잘 이해가 안되고, 계속 삼차원에 집착해서 너무 어렵게 돌아가려고 했었는데, 그냥 노드가 n개인 그래프!! (그치만 가중치가 |xA-xB|, |yA-yB|, |zA-zB|) 셋 중 가장 작은거인) 이라고 의식하고 나니 쉽게 이해가 갔다.
코드
import sys
#해당 노드의 부모를 찾는다.
def find_parent(parent, x):
if parent[x]!=x:
parent[x]=find_parent(parent,parent[x])
return parent[x]
#노드를 연결시켜줬으니 부모배열도 업데이트 시켜준다.
def union_parent(parent,a,b):
a=find_parent(parent,a)
b=find_parent(parent,b)
if a<b:
parent[b]=a
else:
parent[a]=b
n=int(sys.stdin.readline().rstrip())
#부모 배열 초기화
parent=[0]*n
for i in range(n):
parent[i]=i
edges=[]
result=0
x=[]
y=[]
z=[]
for i in range(n):
location=list(map(int,sys.stdin.readline().split()))
x.append((location[0],i))
y.append((location[1],i))
z.append((location[2],i))
#x,y,z 위치를 각각 오름차순으로 정렬
x.sort()
y.sort()
z.sort()
for i in range(n-1):
#x,y,z 각 간선의 길이를 추가시켜줌 -> 모든 간선을 추가시킬 수 없기 때문에
#좌표 자체를 먼저 정렬시킨 것
edges.append((x[i+1][0]-x[i][0],x[i][1],x[i+1][1]))
edges.append((y[i+1][0]-y[i][0],y[i][1],y[i+1][1]))
edges.append((z[i+1][0]-z[i][0],z[i][1],z[i+1][1]))
#가중치 정렬
edges.sort()
for edge in edges:
cost, a, b = edge
#해당 노드의 부모를 찾아 노드를 연결하면 사이클이 생기는지 확인한다.
if find_parent(parent,a)!=find_parent(parent,b):
union_parent(parent,a,b)
result+=cost
print(result)#3665 최종 순위
🔗https://www.acmicpc.net/problem/3665
문제
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.
올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.
창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.
입력
첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 팀의 수
n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500) - n개의 정수
ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. - 상대적인 등수가 바뀐 쌍의 수
m(0 ≤ m ≤ 25000) - 두 정수
ai와bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.
출력
각 테스트 케이스에 대해서 다음을 출력한다.
- n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면
"?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는"IMPOSSIBLE"을 출력한다.
생각
하하하하하하 레전드
도저히 감이 안와서 해설을 참고 하였습니다
해설을 본 후 위상정렬을 응용하면 되겠다 라는 것을 인지 후
해당 영상 참고를 해 이해하였습니다!!
- 상대적인 순위가 바뀌었다. -> 그래프 내의 해당 팀간의 간선의 방향을 뒤집어 준다.
- 확실한 순위를 찾을 수 없다. -> 위상 정렬의 결과가 여러개이다. -> 큐에 여러개의 노드가 들어가 있다.
- 데이터에 일관성이 없다. -> 그래프 내 사이클이 발생해 위상 정렬을 찾을 수 없다. -> 노드를 다 탐색하기 전에 큐가 비어버린다.
이 세가지를 이해하는게 핵심이었던 것 같다..
코드
import sys
from collections import deque
t=int(sys.stdin.readline().rstrip())
#위상정렬함수
def topology_sort():
result=[]
q=deque()
#위상 정렬 결과가 하나인가
certain=True
#그래프 내 사이클이 존재하는가
cycle=False
#진입차수가 0인 노드를 처음에 큐에 삽입한다.
for i in range(1,n+1):
if indegree[i]==0:
q.append(i)
#노드(팀)의 개수만큼 반복
for i in range(n):
#만약 큐가 먼저 끝나버리면, 사이클이 발생한 것
if len(q)==0:
cycle=True
break
#큐에 노드가 두개 이상이라면, 가능한 정렬 결과가 여러개인 것
if len(q)>=2:
certain=False
break
#큐에서 원소 꺼낸다.
now = q.popleft()
result.append(now)
#해당 원소와 연결된 노드들의 진입차수에서 1 뺀다.
for j in range(1,n+1):
if graph[now][j]:
indegree[j]-=1
#새롭게 진입차수가 0이되는 노드를 큐에 삽입한다.
if indegree[j]==0:
q.append(j)
if cycle:
print("IMPOSSIBLE")
elif not certain:
print("?")
else:
for i in result:
print(i,end=' ')
print()
for tt in range(t):
#팀 갯수
n=int(sys.stdin.readline().rstrip())
#진입차수 초기화
indegree=[0]*(n+1)
#인접행렬 초기화
graph=[[False]*(n+1) for i in range(n+1)]
#전 순위 입력
rank=list(map(int,sys.stdin.readline().split()))
#방향 그래프의 인접 행렬 업데이트
for i in range(n):
for j in range(i+1,n):
graph[rank[i]][rank[j]]=True
#진입 차수 1 증가
indegree[rank[j]]+=1
#변경된 순위 입력
c=int(sys.stdin.readline().rstrip())
#간선의 방향 뒤집어야함
for i in range(c):
a,b=map(int,sys.stdin.readline().split())
#인접행렬을 통해 간선 유무 확인 후, 있는 곳을 뒤집어 준다.
if graph[a][b]:
graph[a][b]=False
graph[b][a]=True
indegree[a]+=1
indegree[b]-=1
else:
graph[a][b]=True
graph[b][a]=False
indegree[a]-=1
indegree[b]+=1
topology_sort()