깜태

문제링크 : www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 푸는 방법 자세히 보면 수는 0으로 시작할 수 있다는 말이 있는데, 이는 01 02 03 04 05 도 가능하다는 말이 됩니다. 엥?? 그럼 1로 시작하는 건 당연히, 12 ~ 19까지, 2로 시작하는건 22~ 29 까지 8로 시작하는건 89까지 입니다. 그럼 [i][n]에 해당하는 값은 i-1에서 n~9까지의 값을 더하면 됩니다. 이전에 계단수 문제를..

문제 링크 www.acmicpc.net/problem/19947 푸는 방법 DP를 이용해 해당 년도에 얻을 수 있는 최대값을 구하면 됩니다. 점화식은 다음과 같습니다. dp[i] = max(dp[i-1]*1.05, dp[i-3]*1.2, dp[i-5]*1.35) 만약 10000원과 6년이 주어졌다고 하면, 1년 뒤에 얻을 수 있는 최대 금액은 dp[1] = dp[0] *1.05 = 10,000 * 1.05=10,500, 2년 뒤에 얻을 수 있는 금액은 dp[2] = dp[1] * 1.05 = 10,500 *1.05=11,025, 3년 뒤에 얻을 수 있는 금액은 dp[3] = max(dp[2] * 1.05 , dp[0] * 1.2) = max(11,025 * 1.05, 10000*1.2) = max (11..

문제 링크 : www.acmicpc.net/problem/19621 처음 접근한 방법은 완전탐색 알고리즘이였습니다. 가능한 경우의 수를 나열해보자는 방식이였는데, 경우의 수를 알아야 나열할 수 있는데 자꾸 재귀적으로 짤 수 밖에 없었고, 방법이 잘못되었단 생각이 들었습니다. 결국 실패해서 검색해보고 접근방법을 깊이우선탐색(DFS)로 변경하여 배웠습니다. [참고] [1]: jinho-study.tistory.com/926, [2]: txegg.tistory.com/138 푸는 방법 각 시간을 기준으로 잡았을 때 가능한지를 탐색해야 합니다. 1. 알고리즘 상의 탐색할 데이터의 끝을 설정하여, 끝에 다가갔다면 마지막 값을 리스트에 담습니다. 2. 끝이 아니라고 생각하면, 현재 값을 계속 추가해가며 더합니다. ..

링크 : www.acmicpc.net/problem/1912 처음엔 쉬운줄 알고, 완전탐색 알고리즘으로 O(N^2)의 시간을 알고리즘을 짰더니 타임아웃 에러로 안 됐었습니다. 다 풀고나서 보니 알고리즘도 썩 좋지 않네요 ㅎㅎ (타임아웃 난 코드) N = int(input()) data_list = list(map(int, input().split()))[:N] sum_list = list() for i in range(N): max_sum = data_list[i] for j in range(1, N): if max_sum < sum(data_list[i:i+j]): max_sum = sum(data_list[i:i + j]) sum_list.append(max_sum) print(max(sum_list..

링크 : www.acmicpc.net/problem/14889 푸는 방법은 다음과 같습니다. 1. 먼저 배열을 입력받습니다 2. 4번줄 cases는 N명을 각각 N/2, N/2로 나누었기 때문에 팀이 생길수 있는 경우의 수를 나열해야 합니다. 경우의 수를 나열하는데에는 itertools 라이브러리를 이용해 편하게 생성하였습니다. 저의 경우는 A팀을 생성하면 , 나머지가 B팀이 되도록 만들었습니다. (6명이라 하면, A팀으로 (0, 2, 4) 가 생성될 경우, 자동으로 B팀은 나머지인 (1,3,5)가 됩니다) 3. 최소격차는 임의로 큰 값을 넣어도 되는데, 행렬 1개의 cell 값이 100을 넘지 않는다길래, N*N*100이 최대값이라 생각하고 이보단 작을 거라 생각한 최대값을 넣었습니다. 4. 9번 줄에..