전체 글
-
2225 - 합분해Programming/BackJoon 2023. 3. 20. 14:07
1) 문제 설명 특정 수를 몇개로 만들 수 있는지 구하는 것 0도 허용되고, 중복이 허용되고, 여러번 사용도 가능 예를 들어서, n = 1이고, k = 2이면 -> 1을 0,1만 써서 만드는 방법의 수를 구해야한다. 0+1, 1+0 => 2가지 n=1이고, k=3이면, 3가지이다. n=1,k=2보다 1개가 더 늘어난다. 0+0+1, 0+1+0, 1+0+0 다른 경우를 따져보면, n = 2, k = 2이면 2를 만드는데, 0,1,2를 사용하는 경우를 찾는것 0+2, 2+0, 1+1 -> 3가지 n = 2, k = 3이면, 총 6가지가 나온다. 0+0+2, 0+2+0, 2+0+0, 0+1+1, 1+0+1, 1+1+0 표로 그려보면 더 쉽게 점화식이 보인다 가로축이 n이고, 세로가 k이다. (n을 k개의 숫자..
-
1699 - 제곱수의 합Programming/BackJoon 2023. 3. 17. 10:35
1) 문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 2) 문제 설명 어떤 자연수를 제곱수로 나타낼 수 있다 ex ) 11 = 3^2 + 1^2 + 1^2 -> 3개로 가능 3) 문제 풀이 처음에는 받은 수 n 의 sqrt를 구해서 해볼 생각이었다. (수학 + 구현 문제인줄..) 예를 들어서 11이면 int(math.sqrt(11)) = 3 11 - 3^2 = 2 int(math.sqrt(2))..
-
2579 - 계단 오르기Programming/BackJoon 2023. 3. 16. 13:58
1) 문제 설명 계단을 오르는 데 조건이 있다 계단은 한번에 한 계단 혹은 두 계단씩 오를 수 있다. 한 계단을 밝으면 그 다음 혹은 그 다음 다음 계단을 밟을 수 있다 연속된 세개 계단은 밟을 수 없다 마지막 계단은 반드시 밟아야 한다 2) 문제 이해 조건에 왜 마지막 계단을 밟아야 되는지를 주었는지 모르겠다 일단 dp 문제라고 이해하고, 규칙을 찾아본다 첫번째 계단은 밟거나 밟지 않을 수 있다. (2 계단을 건너뛸 수도 있으므로..) 두번째 계단은 첫번째 계단을 밟고, 또 밟을 수 있다. 그리고 두번째 계단만 밟을 수도 있다. 세번째 계단은 첫번째 계단을 밟고, 2칸을 건너뛴 다음에 세번째를 밟을 수 있고 2번째 계단을 밟고, 3번째 계단을 밟는 경우가 있다. 네번째부터는 점화식을 세울 수 있다 경우..
-
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번째 열에서는 일부러 선택을 안한다. 왜냐하면 마지..