Programming/BackJoon
-
1912 - 연속합Programming/BackJoon 2023. 3. 15. 14:48
1) 문제 설명 주어진 수들 가운데, 연속적으로 더했을때 가장 큰 수를 찾는 문제 전형적인 dp 문제 특정 위치에서 연속합은 내 앞에껄 가져와서 더하거나 혹은 나만 더하거나 이다. dp[0]은 list[0]과 같고 dp[1] = max(dp[0] + list[1] , list[1]) dp[2] = max(dp[1] + list[2] , list[2]) 점화식을 세워보면 dp[n] = max(dp[n-1] + list[n] , list[n]) 이다 2) 문제 풀이 import sys n = int(input()) lst = list(map(int, sys.stdin.readline().split())) dp = [0] * (n) dp[0] = lst[0] max_value = dp[0] for i in r..
-
1966 - 프린터 큐Programming/BackJoon 2023. 3. 15. 08:43
1) 문제 설명 프린터 작업을 하는데, 우선순위를 두고 해야한다. 주어진 프린터 작업 리스트 중에서 우선순위가 가장 높은것부터 출력하고, 내 뒤에 나보다 우선순위가 높은게 있으면 출력하지 않는다. 2) 문제 분석 Queue를 사용해서 푸는 문제 우선순위까지는 알겠는데, index를 어떻게 같이 저장할 것인지 고민 필요 -> 튜플형태로 (value, idx)로 저장 enumerate를 사용해서 idx와 우선순위를 쉽게 저장할 수 있다. lst = [1,2,3,4] for idx, value in enumerate(lst): print(idx, value) 우선순위를 튜플에 먼저 저장한 이유는 max값을 찾을때 쉽게 하려고 그랬다 import sys t = int(input()) while t > 0: n,..
-
2156 - 포도주 시식Programming/BackJoon 2023. 3. 14. 14:39
1) 문제 설명 - 포도주를 마시는데, 최대로 마실 수 있는 양을 구하는 문제 - 단, 조건은 3잔 연속 마실 수 없다. - 예를 들어서, 1,2,3 의 포도주가 있으면 1+2+3 => 불가 (3잔 연속으로 마실 수 없음) 1+ 3 => 가능 2+3 => 가능 - 위 경우 답은 5이다. 문제에 나온 케이스를 가지고 분석해보면, 2) 문제 구현 - dp[0]은 입력받은 값의 0번째가 무조건 들어간다. (dp[0] = input[0]) - 1일 때는 max(input[1] + dp[0]) - 2일 때는 고려할게 하나 더 늘어난다. 3번 연속 마시는 경우를 고려해야한다. input[2]+input[1], input[2] + input[0], dp[1] 2번째와 첫번째 잔을 마시거나 2번째와 0번째 잔을 마시거..
-
9465 - 스티커Programming/BackJoon 2023. 3. 14. 13:25
1) 문제 설명 - 스티커를 선택하는데 최대 점수로 선택했을 때 점수를 출력! - - 위 그림에서는 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 2) 문제 아이디어 - DP로 풀수 있으며, 선택의 문제이다. - 점수를 규칙대로 채우면 마지막 값만 비교하면 된다. 처음에는 기본 값을 넣어준다 2번째 항에는 1번째 항의 결과값과 조건으로 주어진 점수표를 더해서 넣으면 된다. 단, 인접항 항은 더할 수 없으므로 대각선으로만 더해서 나간다. 예를 들면 dp[0][1]에 올수 있는건 dp[1][0] + 첫번째라인[1] 이다 문제에서 보면 3번째 열 이후에는 한번 선택을 하지 않는다. 그림으로 설명해보면, 4번째 열에서는 일부러 선택을 안한다. 왜냐하면 마지..