[백준/Pyhon] 14002 가장 긴 증가하는 부분 수열 4
문제 링크 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 최대 길이를 구하려면 현재 위치의 값에서 앞에 작은 값들이 얼마나 있는지를 계산하면 된다. 수열 10, 20, 10, 30, 20, 50이 있다고 가정한다. 첫 번째 위치인 10은 자신 하나므로 최대 길이가 1이 되고, 두 번째 위치인 20은 자신과 그 앞의 숫자로 최대 길이가 2가 된다. 세 번째 위치인 10은 앞의 두 숫자가 모두 작지 않으므로 최대 길이가 ..
[백준/Python] 2251 물통
문제 링크 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 풀이 물을 옮기는 경우는 A에서 B, C로, B에서 A, C로, C에서 A, B로 총 6가지가 존재한다. A에서 B로 물을 옮긴다고 한다면, 현재 A에 들어있는 물의 양과 B의 컵의 양에서 들어있는 물의 양을 뺀 만큼의 양 중에서 더 작은 값만큼 옮겨지게 된다. 물을 옮긴 후에 현재 각 컵에 들어있는 물의 양이 전에도 나왔던 값인지를 비교한 후, 나오지 않았다면 큐에 추가한다. 위 과정을 큐가 비어있을 때까지 반복한다. 전체 ..