깜태

푸는 방법 DP(Dynamic Programming)을 이용하여 행이 증가될 때마다, 최고의 값을 구합니다. 행을 거듭해가며 더할 때마다 삼각형을 해체해서 경우를 살펴보면 다음과 같습니다. 1. 왼쪽으로만 진행하는 경우 3. 오른쪽으로 증가하는 경우 에는 단순하게 이전행의 마지막값을 더해주면 됩니다. 하지만 2번 같이 값이 겹쳐지는 경우에는 각각 더했을 때 최대가 되는 경우를 비교해 선택하면 됩니다. 코드 n = int(input()) tri = [] for _ in range(n): tri.append(list(map(int, input().split()))) for i in range(1, n): for j in range(i+1): if j==0: #왼쪽 행 tri[i][j] +=tri[i-1][j..

링크 : www.acmicpc.net/problem/14502 푸는 방법 해당 문제가 왜 브루트포스에 있는가부터 고민을 하다가 해결하게 되었습니다. 벽을 3개 설치한다는 것은 0으로 되어있는 빈 공간 중 3개를 설치하는 것을 의미하고, 0인 행렬 포지션들을 나열해서 그중 3개를 선택하는 순열을 이용했습니다 그 다음, 백트래킹을 이용해 바이러스가 퍼지는 알고리즘을 설계하여 퍼뜨린 후 그 내부 안에서 0의 숫자를 세서 순열 중에서 최고값을 반환하게 만들었습니다. 나름 가독성 있게 써봤는데, 만족하셨으면 좋겠네요 감사합니다 코드 import itertools import copy N, M = map(int, (input().split())) arr = [0 for x in range(N)] for i in r..

링크 : www.acmicpc.net/problem/18429 푸는 방법 1. N일동안 A개의 운동을 선택해서 진행하므로, itertools를 이용해 순열을 생성합니다. 그리고, 이 경우가 할수 있는 운동의 최대 개수입니다. 2. N일동안 운동하는 중에, 근손실이 발생하면 안되므로 매일마다 운동량이 0보다 작아지는지 확인하고 만약 작아진다면 최대 개수에서 1개씩 뺍니다. 3. 전체 가능한 운동 개수에서 근손실이 발생한 경우를 뺀 나머지를 출력합니다. 코드 import itertools N, K = map(int, input().split()) A = list(map(int, input().split())) cases = list(itertools.permutations(A, N)) count = len(..

링크 : www.acmicpc.net/problem/2231 푸는 방법 1. 숫자를 입력받고, 반복문을 돌며 한자리씩 나눕니다. 2. 각 자리수의 합과 수의 합이 입력받은 숫자와 같다면 생성자 리스트에 추가합니다. 3. 마지막으로 최소값을 반환합니다. 코드 N = int(input()) hap = list() for i in range(N): D = str(i) sum = 0 for x in D: sum += int(x) if sum + i == N: hap.append(i) if hap != []: print(min(hap)) else: print(0)

링크 : www.acmicpc.net/problem/14888 푸는 방법 가능한 연산의 경우를 순서대로 배열해야 되기 때문에, itertools 내부의 permutation(=순열)를 이용합니다. (itertools 라이브러리를 이용하면 편-안하게 다양한 경우의 수를 만들 수 있습니다) 1. 연산자들을 나란히 받아서 하나의 리스트로 합친 후, 다양한 순서 개수를 따져야 하므로 순열로 변환합니다. 2. 경우의 수마다, 하나씩 순차대로 연산을 진행 3. 진행한 값을 최소, 최대값과 비교해가며 갱신한뒤, 마지막으로 출력합니다. import itertools N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, i..

링크 : www.acmicpc.net/problem/3085 푸는 방법 1. 입력을 받습니다. 2. 입력된 행렬 N x N 을 하나씩 다 탐색합니다. 3. 캔디를 옮겨보았을 때, 해당 행렬에 연속된 캔디숫자를 세고 반환합니다. 4. 반환한 연속된 캔디 개수를 최대값과 비교하며 갱신합니다. 코드 N = int(input()) candies = ['0' for x in range(N)] for i in range(N): candies[i] = [x for x in input()] def count_candy(x,y): row_count = 0 col_count = 0 max_count = 0 row_start = candies[0][y] col_start = candies[x][0] for i in rang..

링크 : 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..