전체 글

문제 문제 이해 처음에 7명의 난쟁이로 100을 구하는 방법을 썻는데 3중 for문으로 나와 답이 안나왔씁니다. 고려해야할 경우도 많았구요. 다른 접근방법을 생각해보니 전체 난쟁이 중에서 2명만 거르면 되는거였습니다. 전체 난쟁이의 합 - (다른 난쟁이 2명) 을 하면 진짜 난쟁이는 100의 값을 가질 수 있습니다. 코드 result = [] for i in range(9): result.append(int(input())) sum_a = sum(result) Flag= False for i in range(9): for j in range(i+1,9): if(100 == sum_a -(result[i] + result[j])): result[i] = 0 result[j] = 0 result.sort()..

문제 문제이해 만약 11이라면 3^2, 2^2, 1^1이 몇개있는지 확인해서 가장 적은 수를 찾으면 됩니다. 예를 들면 11에서 3^2가 몇개있는지 확인하려면 10자리에 +1을 하면 됩니다. 2^2가 몇개 있는지 확인하려면 7자리에 +1을 하면 됩니다. 1^1가 몇개 있는지 확인하려면 2자리에 +1을 하면 됩니다. 1을 더하는 이유는 나머지 dp[x] + x*2 로 더하는 경우 (1가지) 의 경우를 더한다고 볼 수 있습니다. 예를 들면 11을 구할 때 10 + 1하면 됩니다. 7 + 2^2 하면 됩니다. 2 + 3^3하면 됩니다. 위 3개중에 가장 작은 경우의 수를 가진것을 뽑으면 됩니다. 코드 n = int(input()) dp = [i for i in range(n+1)] for i in range(..

문제 문제 이해 조금 어렵게 생각했다가 작은 문제로 생각해보니 접근이 어렵지는 않았습니다. 입력 받은 수열 첫 번째 부터 하나씩 더하면서 그 값을 저장하면 됩니다. 코드 test_case = int(input()) dp = list(map(int,input().split())) for i in range(1, test_case): dp[i] = max(dp[i], dp[i] + dp[i-1]) print(max(dp))

문제 문제이해 가장 긴 증가하는 부분 수열과 비슷하빈다. 이번에는 가장 긴 증가하는 부분 수열을 찾아야합니다. 우리는 dp 배열에 각 자리의 수열개수가 들어있다는 것을 압니다. 그러면 주어진 수열을 거꾸로 돌면서 최고 수열 개수인 수를 찾으면 됩니다. 그러니 최고 수열 개수를 1개 찾으면 1을 줄여줘서 다음 수를 찾아 봐야 합니다. 코드 test_case = int(input()) nums = list(map(int,input().split())) dp = [1] * test_case for i in range(1, test_case): for j in range(i): # 자리수 맨 왼쪽부터 들어온다. if(nums[i] > nums[j]): # 자리수 왼쪽부터 체크 dp[i] = max(dp[j]+ ..

문제 문제이해 수열이 주어지면 각 자리수마다 따로 생각해봅니다. 왼쪽으로 더 적은 수가 들어오면 그것이 수열이 됩니다. 처음에 이해가 되지 않아 https://bitwise.tistory.com/215 블로그를 참고했습니다. 코드 test_case = int(input()) nums = list(map(int,input().split())) dp = [1] * test_case for i in range(1, test_case): for j in range(i): # 자리수 맨 왼쪽부터 들어온다. if(nums[i] > nums[j]): # 자리수 왼쪽부터 체크 dp[i] = max(dp[j]+ 1 , dp[i]) # 바뀐 것, 더 큰것 체크 print(max(dp)) # 꼭 끝쪽에 최대 길이 배열이 없..

문제 문제이해 N=1일 때는 1만 있으니 맨 끝자리는 1 N=2일 때는 10, 만 있으니 맨끝자리는 0 ... 이렇게 맨 끝자리를 보면됩니다. 끝자리가 0인 경우 끝자리가 1인 경우 N=1 0 1 N=2 1 0 N=3 1 1 N=4 2 1 N=5 3 2 N=6 5 3 끝자리가 0일 때 0,1 이 들어갈 수 있고 끝자리가 1일 때는 0만 들어갈 수 있습니다. 코드 num=int(input()) d = [[0] * 2 for _ in range(91)] d[1]=[0,1] d[2]=[1,0] for i in range(3,91): d[i][0] = (d[i-1][0]+d[i-1][1]) d[i][1] = (d[i-1][0]) print((sum(d[num])) )

문제 문제 이해 0을 제외한 모든 숫자는 앞에 올 수 있다. 이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1). 하지만 9 뒤엔 오직 숫자 8만이 올 수 있다. dp테이블은 이차원 리스트이며 dp[자리 수][앞에 오는 숫자]=경우의 수입니다. 앞에 오는 숫자 = 0 ) dp[자리 수][0] = dp[자리 수 - 1][1] ※ dp[1][0] = 0이기 때문에 어차피 결과엔 영향을 미치지 않는다. ex) 0, 01, 012 -> 안 셈! 앞에 오는 숫자 = 1~8 ) dp[자리 수][앞에 오는 숫자] = dp[자리 수 - 1][앞에 오는 숫자 -1] + dp[자리 수 - 1][앞에 오는 숫자 + 1] dp[n][i] = dp[n][i-1] + dp 앞에 오는 숫자 =9 ) dp[자리 수][9..

문제 문제이해 dp[1] 1 1개 dp[2] 2 2개 1+1 dp[3] 3 4개 1+2 2+1 1+1+1 dp[2]에 1 더해주기 dp[4] 1+3 3+1 1+2+1 2+1+1 1+1+1+1 dp[3]에 1 더해주기 7개 2+2 1+1+2 dp[2]에 2 더해주기 dp[5] 1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2 dp[4]에 1 더해주기 13개 3+2 1+2+2 2+1+2 1+1+1+2 dp[3]에 2 더해주기 2+3 1+1+3 dp[2]에 3 더해주기 여기에서 중복을 제외해야 합니다. 5를 예를 들면 dp[4]에서 마지막 값이 1인 것은 제외해야합니다. dp[3]에서 마지막 값이 2인 것은 제외해야합니다. dp[2]에서 마지막 값이 3인 것은 제외해야합..

문제 문제이해 카드의 개수(N)를 구해야 합니다. 1부터 순서대로 카드팩안에 카드들이 있습니다. 동일한 개수인데 가장 적은 금액을 내야한다고 합니다. 일단 카드의 개수 안에서 낼 수 있는 금액들을 추려봅니다. 그 다음 최소값을 구하면 됩니다. ex) 카드 4개를 사야하고 카드팩1 = 1원, 카드팩2 = 5원, 카드팩3 = 6원, 카드팩4 = 7원 인 상황입니다. 카드 1개를 샀을 때 카드팩1 1개이니 1원이 최소값입니다. 카드 2개를 사야할 때 (카드팩1) * 2, (카드팩2) 2개의 상황이 주어지는데 카드팩 2의 금액이 작으니 (카드팩1) * 2를 골라줍니다. 카드 3개를 사야할 때 (카드팩1) * 3, (카드팩2 + 카드팩1), (카드팩3) 3개의 상황이 주어지는데 (카드팩1) * 3이 가장 큰 금액..