궤도

문제 풀이 문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다. 근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 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..

문제 풀이 먼저 모든 친구 관계를 저장한다. 메모리를 아끼기 위해 myunji.tistory.com/291?category=1154147 [백준] 1707번 : 이분 그래프 문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으 myunji.tistory.com 이때 썼던 방법으로 저장했다. i번째 사람을 시작점으로 하는 dfs를 N번 돌리면서 문제의 조건에 맞는 친구 5명을 찾으면 리턴한다. 문제를 풀고 다른 사람들의 코드를 보니 친구 관계 4개를 찾는걸 종료 조건으로 한 사람들이 많았다. 근데 그거나 이거나 같은 말이니까 상관없다. 소스코드 #include #include u..

문제 풀이 예제 입력 2에 대해 그냥 중복 상관없이 모든 수열을 사전순으로 출력하면 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 가 될 것이다. 여기서 중복을 제거해야 하는데 처음엔 아무리 머리를 굴려봐도 비효율적인 방법만 떠올랐다. 출력한 수열을 모두 저장해서 비교한다거나...각 숫자의 등장횟수를 세서 계산한다거나... 그러다가 백트래킹 과정을 그림으로 그려봐야겠다 싶었다. 현재 1을 선택한 상황에서 백트래킹으로 7을 선택했다. (1-7) 그리고 더 이상 고를 필요가 없으니 다시 1로 올라와서 9로 내려간다. 9가 선택된 상태이다. (1-9) 또다시 1로 올라와서 9를 선택하려고 보니 이전에 선택한 값과 같은 값이다. 이러면 탐색을 하지 않는 것이다. 9 1 9..