# 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..

풀이 n번째에 붙게되는 정삼각형의 한 변의 길이는 n-1번째의 최대 길이이다. 길이는 6각형의 각 변의 길이로 경우의 수를 나눌 수 있다고 생각하였다. 0번째는 0, 1번째는 1을 기록해두고 1번째 6가지 변에 0,1,0,1,0,1을 담는다 (한개의 정삼각형이 있는 경우 6가지 변의 길이.) n번째 경우의 수에 대한 메모를 확인한다. 메모가 되어있지 않다면 n-1번째 경우의 수가 메모가 되어있는지 확인한다. 메모가 되어있지 않다면 재귀함수를 이용해 거기 먼저 메모하도록 한다. 메모가 되어있다면 n-1번째 6가지 변이 기록되어 있다는 것을 의미하므로 그 중 가장 긴 변을 찾아 n번째에 기록하고 n번째 6가지 변을 update한다. 메모가 되어 있다면 메모를 리턴한다. (1번째는 1이 기록되어있고 6가지 변..

풀이 방문여부를 DP로 이용하는 BFS SWEA의 보급로 문제의 풀이와 약간 유사하면서 다른 점이 있다 https://tbtb7-sw.tistory.com/95 탐색할 때 다음 지점을 탐색할 때 경우의 수를 나눠야 했고 비용을 기록하는 방식이 약간 달랐다. 첫 지점을 시작으로 주변 점들을 탐색한다. loop가 한번 돌 때 이동한 거리가 같은 경우의 수가 큐에 모두 담겨있고 각 경우를 모두 확인하고 루프를 계속한다.(한턴한턴 진행하는 것 처럼) 현재까지 이동한 거리를 cnt를 이용하여 기억하고 있으며 주변 점을 탐색했을 시 이동 거리를 DP 배열에 기록해둔다. 큐에 있는 탐색할 점의 4방향을 확인한다. 벽을 부순 적이 있을 때 벽이 없는 곳만 방문 가능하다. 벽을 부순 적이 없을 때 벽이 있든 없든 방문 ..

풀이1 첫번째 시도는 DFS와 백트래킹이었다 물론, 입력의 최대가 100 x 100 이므로 제한시간 1초(1억번의 연산) 을 훨씬 넘어설 거라 생각했다. inRange : 범위 안인지 체크하는 함수 isEnd : 마지막 지점인지 체크하는 함수 getResult : DFS, 백트래킹을 이용해서 마지막 지점에 도착했을 때(기저조건) 그때까지 비용과 현재까지의 최솟값과 비교해서 result를 update 하는 함수 역시나 시간초과 코드1 #! Backtracking Algorithm import sys sys.stdin = open('input.txt', 'r') sys.setrecursionlimit(10**6) T = int(input()) dx = [1,0,-1,0] dy =..