궤도

문제 풀이 난이도는 플레티넘이지만 이전에 푼 2문제를 합치면 쉽게 풀 수 있어서 풀었다. myunji.tistory.com/324?category=1154147 [백준] 14002번 : 가장 긴 증가하는 부분 수열 4 문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다 myunji.tistory.com 이 문제에서 수열을 출력해보았고 myunji.tistory.com/270 [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가..

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 단순히 수열의 길이만 구하던 위 문제에서 응용된 문제이다. 처음에는 그냥 length가 늘어날 때마다 dp 배열을 그대로 복사하면 되는거 아닌가? 했다가 반례를 만났다. 10 3 7 4 1 8 이 경우 11053에서 작성한 내 코드 기준 dp를 그대로 복사해오면 1 4 8이란 결과가 나온다. 딱봐도 말도 안된다는 것을 알 수 있다. 그래서 배열의 ..

문제 풀이 문제의 조건에 따르면 스티커를 뗼 수 있는 방법은 OXOX XOXO XOXO OXOX 이렇게 지그재그로 떼는 방법밖에 없다. XXOX XXXX 만약 이 동그라미로 표시한 스티커를 떼고 싶다고 하자. 그럼 그 이전까지의 스티커는 어떤 상태여야 할까? OXOX XXOX XOXX OXXX 이런 모습이어야 할 것이다. 그니까 연속으로 떼거나, 한 칸 건너뛰고 떼거나의 방법이 있는 것이다. 점화식을 작성하면 dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + cost[0][i]; dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + cost[1][i]; 이렇게 된다. dp[0][i]와 dp[1][i]중 더 큰 값이 스티커 점수의 최댓값이다. 소스코..

문제 풀이 myunji.tistory.com/318?category=1154147 [백준] 15988번 : 1, 2, 3 더하기 3 문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호 myunji.tistory.com 이 문제에서 숫자의 연속 등장을 제외해야 하는 문제이다. 숫자의 연속 등장을 제외하기 위해선 마지막에 등장한 숫자가 무엇인지 저장해야 한다. 1, 2, 3 더하기니까 마지막에 등장할 수 있는 숫자 역시 1, 2, 3이다. dp[i][j]에 숫자 i를 1, 2, 3의 합으로 나타낸 경우 중 j+1로 끝나는 것..

문제 풀이 문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다. 근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 AC를 받았기 때문에 내 풀이로 설명한다. 카드 i개를 사는 방법은 다음과 같다. (카드 1개가 들어있는 팩 구매) + (카드 i-1개 구매) (카드 2개가 들어있는 팩 구매) + (카드 i-2개 구매) ... (카드 i-1개가 들어있는 팩 구매) + (카드 1개 구매) (카드 i개가 들어있는 팩 구매) 팩 구매가 P, 카드 구매가 dp라고 놓으면 점화식은 금방 나온다. 근데, 다른 풀이들을 보니 여기까지는 똑같은데 dp[0] 부터 dp[i-1] 까지를 전부 비교하는 코드로 작성하고 있었다. 예시를 쉽게하기 위해 카드가 4개 있다고 하..

문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtr myunji.tistory.com 이 문제를 풀 때는 n이 11보다 작기 때문에 재귀함수로 풀 수 있었다. 하지만 이번엔 n이 1,000,000까지 들어올 수 있기 때문에 재귀함수로 풀면 시간이 너무 오래 걸릴 것이다. 그래서 동적계획법(dp)로 풀어야 한다. 특정 수 i에 대해 i를 1, 2, 3의 합으로 나타내는 방법은 다음과 같다. (i-1을 1, 2, 3의 ..

문제 풀이 이 문제를 풀고나서 다른 사람들의 소스코드를 몇 개 봤다. 근데 다들 큐를 2개 사용하거나, while문을 두번 돌리거나 하는 식으로 홍수의 확산과 고슴도치의 이동을 따로따로 관리하는 방법으로 코드를 작성하는 듯 했다. 근데 굳이 그럴 필요 없다. 고슴도치가 없어서 내가 좋아하는 호랑이로 대체했다. 아무튼 이렇게 홍수와 고슴도치의 초기 상태가 주어졌다고 하자. 큐에 홍수의 위치 정보를 먼저 넣고 고슴도치의 위치 정보를 넣었다. 큐의 맨 앞에 있는 파도가 빠지고 새로운 파도의 위치 정보가 큐에 삽입된다. 이런식으로 하면 큐 하나로 홍수와 고슴도치를 관리할 수 있다. 한편, 이렇게 이전에 고슴도치가 방문한 곳이 홍수에 잠길 수도 있다. 그렇기 때문에 고슴도치의 visited는 다른 배열에 저장해서..

문제 풀이 이 문제의 목적은 최단경로를 찾는게 아니라 최소파괴경로를 찾는 것이다. 그니까 아무리 돌아가는 길이라고 해도 벽을 덜 부수는 경로를 우선으로 해야한다. myunji.tistory.com/289 [백준] 2206번 : 벽 부수고 이동하기 문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신 myunji.tistory.com 이 문제랑 헷갈리면 안된다. 아무튼 벽을 안부수는 길을 우선시 해야 한다는 가중치 조건이 생겼지만, 벽을 부순다 or 안부순다 2가지 경우만 있으므로 덱을 사용한 0-1 너비 우선 탐색을 할 수 있다. 길로 갈 때는 덱의 앞에 삽입하고, ..