2019 카카오 신입 공채 무지의 먹방라이브 # 20210125 # CHAPTER11 Greedy # Q06 무지의 먹방라이브 # 먹어야 할 음식 N개 # K ~ K+1 초에 먹을 음식 번호는? import sys sys.stdin = open("input.txt", "r") def solution(food_times, k): answer = -1 size_list = sorted(list(set(food_times))) number_of_sizes = [0] * (size_list[-1] + 1) for n in food_times: number_of_sizes[n] += 1 # print(number_of_sizes) # 누적배열만들기 for idx in range(len(size_list) - 1,..

# 20210124 # CHAPTER11 Greedy # Q04 만들 수 없는 금액 # 동전 N개 # 1 현재 수를 더한 것이 가장 큰 수가 될 수밖에 없음. import sys sys.stdin = open("input.txt", "r") def getResult(_list): ret = 0 max_n = 0 for n in _list: if max_n + 1 >= n: max_n += n else: ret = max_n + 1 break return ret N = int(input()) input_list = list(map(int, list(input().split()))) input_list.sort() print(getResult(input_list))

# 20210124 # CHAPTER11 Greedy # Q03 문자열 뒤집기 # 1

# 20210124 # CHAPTER11 Greedy # Q02 곱하기 혹은 더하기 # 1 0: ret *= n else: ret += n return ret input_list = list(map(int, list(input()))) print(getResult(input_list))

# 20210124 # CHAPTER11 Greedy # Q01 모험가길드 # 1 max_N: max_N = n if cnt >= max_N: ret += 1 cnt = 0 return ret N = int(input()) input_list = sorted(list(map(int, input().split()))) print(getResult(input_list))

https://www.acmicpc.net/problem/11729 풀이1(실패) 분할정복은 문제를 정확히 쪼개서 올바른 결과값을 만들어내야 한다. 상태공간트리를 그려보고 쪼개어져 들어가는 문제들은 작아져야 하고 작은 문제가 가져온 결과를 이용해 정확한 결과를 만들어야 한다. 첫번째 시도 재귀함수를 이용해서 n-1만큼 from에서 to가 아닌 next에 옮기고, 하나를 from에서 to로 옮기고 n-1만큼 next에서 to로 옮기도록 했다. 이렇게 하다보니 어디부터 어디까지 옮겨야할 지가 애매해서 n=5가 넘어가면서 동작하지 않게 되었다. 상태공간트리를 그려보지 않고 설계했을 때 허점이 많았다. 코드 //! 2020.03.20 // TODO BJ11729_하노이탑이동순서 /* 분할정복 알고리즘을 잘못 구..

풀이 DP 1번째부터 N번째까지 물품을 담을 때 담을 수 있는 최대 가치를 기록한다. 담을 때 이전까지 담은 물품들의 무게합들의 경우의 수에 기록된 DP(해당 무게에서의 최대 가치)를 확인한다. DP 값에 현재 물품의 무게를 더한 값에 있는 가치와 비교해서 큰 값을 담는다. DP에 있는 값 중에 가장 큰 값을 출력한다. 코드 //! 2020.03.17 // TODO BJ12865_평범한배낭 #include #include using namespace std; const int MAX = 100050; int N,K; int DP[MAX]; pair inData[105]; int getMax(int n1,int n2){ if(n1>n2) return n1; else return n2; } int getRe..

풀이 백트래킹 + DP A,B 두 문자열을 받고 각각의 index를 분리해서 메모했다. DP[indexA][indexB] : A 문자열의 indexA번째 문자부터 끝까지와 B 문자열의 indexB번째 문자부터 끝까지 중 가장 긴 LCS의 길이 라고 DP를 정의했다. 백트래킹으로 탐색하며 DP를 채워나가도록 처리했다. A[idxA]와 B[idxB]가 같은지 확인한다. 같다면 초기값을 1+ (idxA+1,idxB+1)에서의 LCS 다르다면 (idxA+1,idxB) 과 (idxA,idxB+1)에서의 LCS 중 큰 값 1에서 얻은 결과들 중 가장 큰 값을 현재 index에서의 LCS로 메모한다. idxA와 idxB가 문자열 끝까지 갔다면 0을 리턴한다. 처음부터 끝까지 두개의 문자열 모두 탐색하면 최댓값을 구할..

풀이 input의 최대는 100개의 숫자이고 숫자의 범위는 500이하였다. 처음에 생각했던 풀이는 백트래킹에서 DP를 사용하려고 했었다. n번째부터 마지막까지 전깃줄이 꼬이지 않도록 제거해야 하는 전깃줄의 최솟값을 메모하려했다. 하지만 이를 활용해서 다음 정답을 만드는 점화식이 성립하지 않는다는 생각이 들었다. A를 기준으로 정렬했을 때 B에서 LIS를 구하면 전깃줄이 꼬이지 않게 된다. 그래서 LIS를 구하고 이 길이를 전체 길이에서 뺀 값이 정답이 된다. LIS를 구하는 DP 알고리즘은 다음과 같이 구현하였다. 1번째 숫자부터 N번째 숫자까지 돌면서 LIS를 구한다. K번째 숫자를 맨 오른쪽 끝으로 하는 LIS를 DP배열에 메모한다. K번째 숫자보다 작은 숫자들의 DP를 모두 탐색한다. 그 중 가장 ..

풀이 백트래킹 & DP 0번째 집부터 차례대로 N-1 까지 칠한다. (재귀함수의 기저조건이 n>=N return 0이 된다.) k번째 집을 칠할 때 이전에 칠한 색을 prev로 받고 prev일 때 k번째 칠할 수 있는 경우의 최솟값이 DP에 있는지 확인한다. 있다면 그 값을 return한다. 없다면 백트래킹으로 현재 비용+다음 최솟값 중 가장 작은 값을 구해서 기록하고 return한다. 최소 결과를 출력한다. 코드 //! 2020.03.12 // TODO BJ1149_RGB거리.cpp #include using namespace std; const int MAX = 1050; const int INF = 987654321; int N; int myMap[MAX][3]; int DP[3][MAX]; int..