10000이하의 자연수를 1, 2, 3으로 표현하는 경우의 수를 구하는 문제다. 3까지는 누구나 쉽게 어떻게 표현할 수 있는지 알 수 있다. 4에 대해 살펴보자. 4 = 1+1+1+1 = 2+1+1 = 2+2 = 3+1 로 표현할 수 있다. 여기서 파악해야 할 것은 -1로만 이루어진 식 -2이하의 수로만 이루어진 식(2를 반드시 포함) -3이하의 수로만 이루어진식(3을 반드시 포함) 위의 3가지 식만으로 주어진 수를 표현할 수 있다는 점이다. 이에 기인하여 dp[10001][4] 배열을 선언할 것이다. dp[i][j]에서 i는 주어진 자연수 n이고, j는 위에서 설명한 1, 2, 3으로 이루어진 식의 개수를 의미한다. dp[i][1]을 먼저 생각해보면 dp[i][1] = dp[i - 1][1] 임을 쉽게..

문제가 쉽다고는 느껴지지 않았지만, 정답을 맞추는 것은 쉬웠다. 먼저 문제를 정확하게 이해해야 하는데 각자 돌을 1개 또는 3개만 가질 수 있다. 따라서 마지막에 돌이 2개 남는다면 2개를 모두 가져오지 못하고, 1개만 가져올 수 있다. 예를 들어 n = 2 라면 승자는 반드시 창영이다. 문제를 보면 두 사람 모두가 최선의 선택을 한다고 가정을 하는데 '최선이라는 것을 어떻게 정량화하여 구현할 것인가' 라는 고민을 가진 채로 문제를 풀기 시작했다. 처음에는 돌을 5개로 가정하고 모든 경우를 따져보았다. 모든 경우에서 상근이가 이긴다. 돌이 6개인 경우에는 창영이가 반드시 이긴다. 나는 여기서 최선의 선택을 할 필요없이 돌의 개수에 따라 반드시 승자가 한명일 것이라고 추측했다. 다시 돌 1개부터 승자가 누..

문제를 보고 가장 먼저 생각난 방법은 루트노드부터 시작해서 가장 큰 간선의 가중치로 해당 레벨의 모든 간선의 가중치를 갱신하는 것이었다. 근데 좀만 생각해봐도 이렇게 하면 너무 커짐을 생각해볼 수 있다. 이 문제의 예제 그림을 보면 약간의 힌트를 얻을 수 있다. 잘 보면 값이 가장 하위 레벨의 노드부터 갱신됨을 알 수 있다. 가장 하위 레벨의 노드부터 값을 갱신해야만 가장 최소한의 가중치 증가가 이루어진다. 위의 그림을 예로 들어보자. 루트노드부터 갱신을 진행하면 하위 4개의 모든 간선의 가중치가 3이어야하고 그러면 총 5가 증가한다. 하위 레벨의 노드부터 갱신을 진행하면 위의 그림과 같이 4의 증가만해도 된다. 따라서 bottom-up 방식으로 간선의 가중치를 갱신해주면 된다. 정답 코드 #includ..

브루트포스로 풀면 당연히 시간초과가 날 것이다. 최악의 경우 O(2^n) 이고, n의 최댓값은 1000이므로 시간초과를 예상할 수 있다. 브루트포스의 과정을 생각해보면 같은 연산을 하게 되는 부분이 분명히 존재할 것이다. 예를 들어 [1, 2, 3, 4, 5, 6] 과 같이 카드가 있다고 가정해보자. 근우가 6, 5 를 가져가고 명우가 1, 2를 가져가는 경우든 근우가 6, 1 을 가져가고 명우가 5, 2를 가져가는 경우든 남아있는 카드는 [3, 4] 이다. 즉, 이전에 어떤 카드들이 선택되었든 남아있는 카드가 동일하다면 해당 카드들을 대상으로는 근우가 얻을 최대 점수는 항상 같을 것이다. 이를 이용해 dp를 활용하면 시간초과를 피할 수 있을 것이다. 나는 game() 이라는 함수를 정의해 dp배열을 채..

기본적인 LCS문제였다. LCS는 쉽게 말하자면 두 수열 모두에게 부분수열이 되는 가장 긴 부분수열이다. LCS에 관한 알고리즘은 유명해서 구글검색을 통해 쉽게 공부해볼 수 있다. 정답 #include using namespace std; string s1, s2; int dp[1001][1001]; void LCS(){ int len1 = s1.length(); int len2 = s2.length(); for(int i = 1; i s1 >> s2; //LCS LCS(); //output cout

어려움. 처음엔 dp[2][1001] 배열로 1이 움직일 때와 2가 움직일 때를 dp로 구현하려 했다. 문제점은 사건을 진행할 때마다 변경되는 각 경찰차의 위치와 사건진행 순서를 관리하기 어렵다는 것이었다. 그러다 기가막힌 방법을 하나 어디서 주워들었다. dp[i][j] 가 1이 i번 사건까지 2는 j번 사건까지 해결했을 때의 최소 거리임을 의미하는 dp[1001][1001] 배열을 만드는 것이다. 즉, 각 경찰차가 마지막으로 진행한 사건 번호를 저장하는 것이었다. 그러면 굳이 좌표를 저장할 필요가 없었다. dfs를 진행하면서 최소 거리를 찾으면서 dp 배열을 채운다. 각 경찰차의 사건 진행 순서도 비슷한 로직으로 구현할 수 있다. 이미 구해진 dp 배열을 이용해서 순서를 구할 수 있다. 코드를 조금씩 ..