WannaBeDeveloper

1103번: 게임 www.acmicpc.net 이 문제는 1부터 9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 할 때 최대 몇 번의 동전을 움직일 수 있는지를 구하는 문제이다. 동전을 움직이는 규칙은 위와 같다. 이 문제를 해결하기 위해서는 왼쪽 위에서 시작하는 DFS를 수행해 동전의 이동 횟수의 최댓값을 구해야한다. DFS는 재귀 함수로 구현할 수 있다. 우선 함수 구현 전에 각 지점을 방문했음을 나타내는 N*M 크기의 visitied 행렬(초기값은 False)과 동서남북 방향을 나타내기 위한 dx, dy가 필요하다. 이제 DFS 함수를 구현해보자. 우선 DFS 함수는 인자로 방문하고자 하는 지점의 좌표 (x, y)를 받는다. 이 지점을 방문했다는 의미로 visited에서 해당하는 지점의 값을 ..

1328번: 고층 빌딩 www.acmicpc.net 이 문제는 높이가 모두 다른 빌딩 N개가 한 줄로 세워져 있고, 이를 왼쪽 끝과 오른쪽 끝에 서서 봤을 때 보이는 빌딩 수를 알 때 가능한 빌딩 순서의 경우의 수를 구하는 문제이다. 이 문제는 단순히 순열과 조합만을 이용해 경우의 수를 구하기는 어렵다. 빌딩의 높이에 따라 가려지는 빌딩이 달라지고, 또한 가려지는 빌딩의 수 역시 고려해야 하기 때문이다. 그래서 다른 방법을 이용해 문제를 해결해야 한다. 어떤 방법으로 해결할 수 있을까? N-1개의 빌딩이 한 줄로 세워져 있을 때 모든 L, R(1

2688번: 줄어들지 않아 www.acmicpc.net 이 문제는 줄어들지 않는 n자리 수의 개수를 구하는 문제이다. 여기서 줄어들지 않는 수란 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같은 수를 말한다. 이는 dynamic programming으로 쉽게 해결할 수 있다. (i+1)자리 수의 맨 앞자리 수가 j일 때 줄어들지 않는 수의 개수를 (i, j) 성분에 저장하는 (n+1)*10 크기의 행렬 dp를 만들고, 초기값으로 dp[0][i] ( i = 0, ... , 9)를 1로 한다. 그 다음 i가 1일 때부터 n일 때까지 순회하면서 (i+1)자리 수의 줄어들지 않는 수의 개수를 구한다. 줄어들지 않는 수의 개수를 구할 때 맨 앞자리의 수가 j로 정해지면 그 뒤자리에 나올 수 있는 수는 j..

11062번: 카드 게임 www.acmicpc.net 이 문제는 근우와 명우가 매번 돌아가면서 일렬로 놓은 N개의 카드 중 왼쪽 끝 또는 오른쪽 끝에 있는 카드를 가져갈 때 근우가 얻는 점수를 구하는 문제이다. 단, 점수는 카드에 적힌 숫자의 합과 같고, 두 사람은 최선의 전략으로 게임에 임한다. 여기서 최선의 전략은 단순히 매번 더 높은 점수가 적힌 카드를 뽑는 전략이 아닌, 전체적으로 가장 높은 점수를 얻기 위해 상대의 선택 역시 고려하면서 카드를 뽑아야 함을 의미한다. 예를 들어 1, 2, 5, 2가 적힌 4장의 카드를 번갈아가면서 뽑을 때, 단순히 오른쪽 끝 카드에 적힌 숫자가 더 크다고 해서 오른쪽 끝 카드를 뽑으면 상대방은 1이 적힌 카드와 5가 적힌 카드 중 5가 적힌 카드를 뽑을 것이고, ..

15486번: 퇴사 2 www.acmicpc.net 이 문제는 N+1일째 되는 날 퇴사하기 전에 남은 N일 동안 상담을 하려고 할 때 얻을 수 있는 최대 수익을 구하는 문제이다. 이 문제는 dynamic programming을 이용해 해결을 해야 한다. 전체 N일 중 각 일자에 대해 순회하면서 i번째 일자에 대해 조사한다고 하자. 우선 i-1번째 일자와 i번째 일자에서의 최대 수익 중 더 큰 값을 dp[i]로 한다. 이는 상담을 할 때 최대 수익을 얻기 위해 꼭 상담을 끝내자마자 바로 그 날의 상담을 시작할 필요가 없기 떄문이다. 그 다음 i번째 일자에 있는 상담을 입력으로 받는다. 그러면 i번째 일자에 있는 상담의 소요 시간 T과 현재 일자를 더한 결과가 N+1을 넘지 않을 때, 즉 퇴사일 전까지 할 ..

1958번: LCS 3 www.acmicpc.net 이 문제는 문자열 3개의 LCS를 구하는 문제이다. 문자열 2개의 LCS를 구하는 방법을 이용하면 문자열 3개의 LCS 역시 쉽게 구할 수 있다. 문자열 2개의 LCS는 두 문자열의 각 문자에 대해 순회하면서 만약 한 문자열의 i번째 문자, 다른 문자열의 j번째 문자가 같은 경우에는 dp[i][j] = dp[i-1][j-1] + 1로 계산하고, 다른 경우에는 dp[i][j]를 dp[i-1][j]와 dp[i][j-1] 중 더 큰 값으로 한다. 문자열이 3개인 경우에도 행렬의 차원을 1 증가시켜 위와 같은 방식으로 하면 된다. 즉, 3개의 문자열의 각 문자에 대해 순회하면서 만약 첫 번쨰 문자열의 i번째 문자, 두 번째 문자열의 j번째 문자, 세 번째 문자..

2502번: 떡 먹는 호랑이 www.acmicpc.net 이 문제는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 먹는 호랑이에게 며칠 째에 몇 개의 떡을 주었는지가 입력으로 주어졌을 때 첫째 날과 둘째 날에 몇 개의 떡을 줬는지를 구하는 문제이다. 단, 문제의 답이 여러 개일 수 있지만 그 중 하나만 출력한다. 호랑이의 조건에서 알 수 있듯이 이 문제는 피보나치 수열의 D번째 항이 주어졌을 때 첫 번째 항과 두 번째 항을 구하는 문제이다. 가장 단순한 방법으로는 가능한 첫 번쨰 항과 두 번쨰 항을 생각해 그 경우에 대해 피보나치 수열을 구하고 특정 항이 원하는 항과 일치하는지를 일일이 보는 방법이 있다. 그러나 이 방법은 특정 항이 K일 때 피보나치 수열을 최대 K^2번 계산해야 하..

2240번: 자두나무 www.acmicpc.net 이 문제는 두 개의 자두나무에서 떨어지는 자두를 각 나무 밑으로 이동해서 받을 수 있고, 나무 밑으로 이동하는 횟수가 제한되어 있을 때 받을 수 있는 자두의 최대 개수를 구하는 문제이다. 이 문제는 dynamic programming으로 해결한다. 우선 궁극적으로 마지막 시간에서 받을 수 있는 자두의 최대 개수을 구하려면 마지막 시간까지 이동한 횟수에 따른 자두의 최대 개수를 구할 필요가 있다. 물론 경우에 따라 이동 횟수가 많은 것이 얻을 수 있는 자두의 개수를 늘리는 결과를 가져올 수 있지만, 오히려 이동 횟수를 줄임으로써 자두를 더 많이 받을 수도 있다. 극단적으로 한 쪽 나무에서만 자두가 떨어지는 경우에는 그 나무 밑에만 서 있어도 최대 개수의 자..

4811번: 알약 www.acmicpc.net 이 문제는 N개의 약을 반씩 쪼개서 먹을 때 2N일 동안 약을 먹는 방법의 수를 구하는 문제이다. 즉, 한 개의 약을 쪼갠 뒤 반을 먹는 경우와 반 개의 약을 먹는 경우를 나눠 N개의 약을 2N일에 걸쳐 먹는 방법의 수를 구한다. 문제에서 나와있듯이 이 문제는 약 한 개를 꺼낸 날을 W, 반 개를 꺼낸 날을 H라 했을 때 N개의 W와 N개의 H를 사용해 만들 수 있는 문자열의 개수와 관련이 있다고 할 수 있다. 단, 이러한 문자열을 만들 때 주의해야 하는 점이 있다. 바로 약 한 개를 꺼내 쪼갠 뒤에야 반 개짜리 약을 꺼낼 수 있다는 점이다. 즉, H는 앞에 나온 W의 개수에서 H의 개수를 뺀 결과만큼만 나올 수 있다. 예를 들어 W가 4개 있고 H가 3개 ..

1256번: 사전 www.acmicpc.net 이 문제는 N개의 "a"와 M개의 "z"로 이루어진 문자열만 알파벳 순서대로 수록한 사전에서 K번째 문자열을 찾는 문제이다. 이 문제를 해결하기 앞서, N개의 "a"와 M개의 "z"로 이루어진 서로 다른 문자열의 개수를 생각해 보자. 만약 N개의 "a"와 M개의 "z"가 모두 서로 다른 문자였다면 N+M개의 문자를 이용해 만들 수 있는 문자열의 개수는 (N+M)!일 것이다. 그런데 N개의 "a"와 M개의 "z"는 같은 문자이므로 이들 사이의 순서가 바뀌어도 같은 경우로 간주할 수 있고 따라서 이 경우의 수를 제외해야 한다. N개의 문자를 나열하는 방법의 수는 N!이므로 전체 경우의 수는 (N+M)!/N!M!이다. 이는 N+M개에서 N개를 택하는 조합의 수와 ..