2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 일단 LIS (가장 긴 증가하는 부분 수열) 의 응용문제이다. 따라서 LIS를 이용해서 풀면 쉽게 풀린다. 전깃줄이 이어져있는 전봇대 A-B 가 주어지면, 전봇대 A 의 위치대로 오름차순으로 정렬을 해준다. 이 때, 전깃줄이 서로 겹치지 않기 위해서는 전봇대 A가 소팅 되었을 때 1-1 2-2 3-3 ... N-N 이렇게 전봇대 B 역시 오름차..
11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제를 풀기전에 먼저 '가장 긴 증가하는 부분 수열' 문제를 풀기를 권장한다! 왜냐하면 해당 문제를 응용해서 푸는 문제이기 때문이다. S1 Sk+1 > ... SN-1 > SN 이렇게 생긴 수열을 바이토닉 수열이라고 한다. 여기서 보이는 규칙은 Sk 값을 기준으로 왼쪽은 '증가하는 부분 수열' 이고 오른쪽은 '감소하는 부분 수열' 이라는 점이다. 그렇다! Sk 값의 가장 긴 바이토닉 부분 수열은 결국 0부터 Sk까지의 가장 긴 증가하는 부..
2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 다이나믹 프로그래밍으로 풀어주는 문제이다. 일단 조건을 살펴보자 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개..
2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 해당 문제에서 유심히 봐야할 조건은 1. 연속으로 3잔을 마실 수 없다. 2. 안마시고 건너뛰어도 된다. 따라서 우리는 현재 n번째 와인을 마실 수 있을 때 세가지의 경우를 고려해볼 수 있다. 첫번째..