궤도

문제 풀이 지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다. 처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다. 일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다. 그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면 이렇게 될 것이다. dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다. 당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다. 한편 예제 입력..

문제 풀이 myunji.tistory.com/208 [백준] 1149번 : RGB거리 문제 풀이 이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다. 보통 문제를 풀 때 0번째가 이거라면 1번째는 myunji.tistory.com 이 문제의 응용 버전이다. 선형으로 배치됐던 집이 이젠 원형으로 배치된다. 고등학교 시절 원순열을 배울 때 선생님이 이런 말씀을 하셨다. "원순열은 시작점이 없어서 헷갈리니까 일단 한 놈을 죽여서 앉힌다고 생각해" 물론 죽인다 식의 표현은 격한 면이 있지만 덕분에 이렇게 몇년이 지난 지금도 잊지 않고 있다. 이 문제의 접근도 똑같이 하면 된다. 일단 첫번째 집의 색을 고정하고 집들을 색칠해 나..

문제 풀이 주어진 예제 입력이 하나인데다가 대충 생각해도 알 수 있는거라 좀 힘들었다. N의 입력이 무조건 짝수인 것만 계산했지 홀수인 경우에 0을 리턴해야 한다는 생각을 못해서 틀리기도 했고... dp배열엔 N/2를 저장할 것이다. 그니까 N=2면 dp[1]에 그 답이 있고, N=4면 dp[2]에 답이 있다. 아무튼 N=2일 때 타일을 채우는 방법은 다음과 같다. N=4라면 일단 처음 3x2를 N=2일 때처럼 채우고, 그 뒤는 dp[1]을 호출하면 된다. 이런식으로... 그럼 여기서 3*dp[1]이 된다. 근데 다른 방법으로도 타일을 채울 수 있다. 이런 모양이 2종류가 있다. 그럼 2*dp[0]을 하면 되는건가?? 여기서 N=6일때로 가면... 이런 것도 가능하고 이런 것도 가능하다. 그럼 dp[i]..

문제 풀이 dp는 점화식을 세우는게 제일 어렵다... 처음엔 2차원 dp배열을 선언해서 세로가 N(i)일 때 사자 j마리를 넣는다면...식으로 생각했지만, 나눠지는 경우의 수가 너무 많았다. dp인데 경우의 수가 일관적이지 않게 나눠진다면 뭔가 잘못하고 있단 뜻이니 바로 방향을 틀어야 한다... 그래서 i번째 줄에 집중하기로 했다. i번째 줄에서 가능한 경우는 3개가 있다. 1. 사자가 없다. 2. 왼쪽에 사자가 있다. 3. 오른쪽에 사자가 있다. 1번의 경우엔 i-1번째 줄에서 사자가 없든 어디에 있든 상관없다. 2번의 경우엔 i-1번째 줄에서 사자가 없거나 오른쪽에만 있어야 한다. 3번의 경우엔 i-1번째 줄에서 사자가 없거나 왼쪽에만 있어야 한다. 정리하자면 dp[100000][3]일 때 dp[i]..

문제 풀이 myunji.tistory.com/319?category=1154147 [백준] 11052번 : 카드 구매하기 문제 풀이 문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다. 근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 AC를 받았기 때문에 내 myunji.tistory.com 이 문제랑 결이 비슷한 것같다. 32를 제곱수의 합으로 나타낸다고 해보자. 일단 6^2 = 36으로 32보다 크기때문에 6을 쓸 순 없다. 그럼 5^2을 쓰면? 32-25니까 7이 남는다. 예제 입력 1을 보면 알겠지만 7을 표현하는 제곱수 항의 최소 개수는 4다. 그렇기 때문에 5^2를 사용하면 4+1 = 5가 될 것이다. 4^2를 써보도록 하겠다. 32-..

문제 풀이 myunji.tistory.com/217 [백준] 1912번 : 연속합 문제 풀이 이것도 유명한 동적계획법 문제인데... 그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자 5, -8, 9, -1, ... 당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 myunji.tistory.com 이 문제에서 숫자를 하나 삭제할 수 있게 됐다. 그래서 del_sum이란 변수를 하나 추가한다. del_sum은 숫자를 삭제했을 수도 아닐 수도 있다. 특정 input이 들어왔을 때 del_sum에 들어올 수 있는 경우는 2가지다. 이 input을 사용하거나 삭제하거나. input을 사용할 때는 del_sum = del_sum+input이다. input을 버릴 땐 del_sum..

문제 풀이 내가 원래 LIS를 풀던 방식으로 풀려다가 엄청난 삽질을 했다. myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이게 내가 원래 LIS를 풀던 방식... 이 문제에선 dp에 최장 길이를 저장할 필요가 없다. 우리가 찾는건 가장 큰 수열의 합이기 때문이다. 그래서 O(n^2)의 시간복잡도로 진행을 할 것이다. 말로 설명하면 어려우니 데이터로 설명하겠다. 1 100 2 50 20 60 3 5 의 데..

문제 풀이 난이도는 플레티넘이지만 이전에 푼 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번 : 가장 긴 증가..