성공 코드(내 코드) #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; answer=n-lost.size(); // lost와 reserve를 오름차순으로 정렬하기 sort(lost.begin(), lost.end()); sort(reserve.begin(), reserve.end()); for(int i=0; i
알고리즘 다이나믹 프로그래밍 풀이 계단 별 점수를 저장하는 벡터 s와 계단 점수의 최대값을 저장하는 벡터 dy를 사용하였다. s[i] = i층 계단의 점수, dy[i] = i층 계단까지의 최대값 dy[1]=s[1] dy[2]=s[1]+s[2] dy[3]=s[3]+(s[1]과 s[2] 중 큰 값) dy[i]=s[i]+(dy[i-2]와 dy[i-3]+s[i-1] 중 큰 값) (n>3) s[i]+dy[i-2] (i 계단의 점수) + (i - 2 계단까지 가는 최대값) s[i]+dy[i-3]+s[i-1] (i 계단의 점수) + (i - 3계단까지 가는 최대값) + (i - 1 계단의 점수) 성공 코드 #include using namespace std; int main() { // freopen("input.t..
알고리즘 다이나믹 프로그래밍 풀이 h 2차원 벡터를 두어 똑같은 색이 이웃하지 않도록 h[i-1]의 값 중 최소 값을 이용하여 값을 누적해간다. 즉, h[i][1]은 i번째 집을 빨간색으로 칠할 때의 최소 비용, h[i][2]은 i번째 집을 초록색으로 칠할 때의 최소 비용, h[i][1]은 i번째 집을 파란색으로 칠할 때의 최소 비용이 된다. 그러면 h[n][1], h[n][2], h[n][3] 중 최소값이 답이 된다. 성공 코드 #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, r,..
알고리즘 다이나믹 프로그래밍 풀이 타일은 | 또는 ㅡ 같은 모양을 가진다. 직사각형 2*n에서 n이 하나 증가하면 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다. 이 외의 경우의 수가 하나 더있는데 = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다. 즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다. 벡터 dy를 이용하여 나타낼 수 있다. dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화 dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다. dy[1]=1 dy[2]=2 dy[n]..
알고리즘 이분 탐색 누적 합 풀이 석순은 아래에서부터 종유석은 위에서부터 자란다. 이를 각각 bottom 벡터과 top 벡터로 나타낸다. 번갈아가면서 석순과 종유석의 길이가 입력되므로 차례대로 입력받은 값을 bottom 벡터 또는 top 벡터에 인덱스로 하여 1씩 더해준다. 실제로 석순의 길이가 3이라면 bottom[1], bottom[2], bottom[3]에 모두 1씩 더해주어야 하는데 이것을 이중 for문으로 다음과 같이 구현하면 시간 초과가 발생하므로 다른 방법을 사용하여야 한다. 시간 초과 코드 #include #include #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync..