궤도

문제 풀이 문제의 조건에 따르면 스티커를 뗼 수 있는 방법은 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 너비 우선 탐색을 할 수 있다. 길로 갈 때는 덱의 앞에 삽입하고, ..

문제 풀이 myunji.tistory.com/287?category=1154147 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제의 응용버전이다. 순간이동과 앞뒤 이동 모두 1초가 걸렸던 1697번과 달리 이번엔 순간이동을 0초만에 할 수 있다. 즉 각 이동에 대한 가중치가 달라진 것인데, 그래프의 관점에서 말하자면 간선에 가중치가 생긴 것이다. 이런 경우에서 최단거리를 찾고자 한다면 가중치가 작은 것을 우선으로 탐색해야 한다. 괜히 가중치 0으로 갈 수 있는 곳을 가중치 ..

문제 풀이 클립보드를 관리하는 것이 중요한 문제다. 처음에는 덮어씌워진다길래 변수 하나로 클립보드를 관리하려 했는데, bfs의 상태에 따라 클립보드의 상태가 다를 수도 있다는걸 생각하지 못한 것이다... 그래서 방문여부를 관리하는 visited 배열을 2차원 배열로 만들어 클립보드의 정보를 저장했다. 그리고 이모티콘의 현상태 정보또한 구조체로 관리했다. 구조체에는 이모티콘의 개수와 그때까지 걸린 시간, 그리고 그 상태에 클립보드에 복사된 이모티콘의 개수를 저장했다. 소스코드 #include #include using namespace std; const int MAX = 1001; struct emoji { int num, time, pasted; }; int S; bool visited[MAX][MAX..