겜돌이의 개발일지

문제 백준 2302 극장 좌석 C++ 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 처음에 dp인지 완전탐색인지 헷갈렸던 문제 최대 21억 개의 가짓 수가 있는 것 보고 dp일거 같았다. 자신의 번호와 다른 자리에 앉을 때는, 항상 그 사람과 나의 자리를 바꿔서 앉는다는 것에 초점을 두고 고민했다. 1, 2, 3 세 명을 자리에 앉힌다고 가정하자. 1과 2, 2와 3을 서로 바꿔 앉게 할 수 있다. 1, 2를 먼저 앉힐 때 1 2 또는 2 1이 가능하다. 이 때 3을 앉힐 때 1 2 뒤에 3을 앉혀 1 2 3을 만..

문제 백준 1937 욕심쟁이 판다 C++ 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 dp와 dfs가 섞인 재밌는 문제이다. dp 배열은 해당 칸에서 판다가 시작할 시에, 먹을 수 있는 최대 대나무를 가지고 있는 배열이다. (-1로 초기화) dfs를 돌면서 다음과 같은 과정을 거친다. 1. 어느 곳에서 시작하든, 자기 자신 칸에 있는 대나무는 먹을 수 있다. 따라서 dp 배열의 최소값은 1이다. result 값을 먼저 1로 설정한다. 2. 상하좌우 순으로, 다음값이 현재값보다 크다면 둘 중..

문제 백준 11058 크리보드 C++ 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 풀이 DP 문제인데 점화식을 떠올리기가 어려웠다. 처음에 방문체크를 해주는 BFS로 풀려고 했지만... 경우가 많아도 너무 많아서 포기 dp[i]의 최댓값은 다음 중 하나이다. 1. dp[i-1] + 1 2. Ctrl + A, Ctrl + C의 2단계를 거쳐 복사, Ctrl + V로 한 번 붙..

문제 백준 5582 공통 부분 문자열 C++ 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 예제 입력을 보겠습니다. A B R A C A D A B R A E C 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 B 1 1 R 1 1 B 1 1 C 1 R 1 1 D 1 A 1 1 1 1 1 R 1 1 A 1 1 1 1 1 s1를 문자열 1의 길이, s2를 문자열 2의 길이라고 하면 dp[0][0] 부터 dp[s2-1][s1-1] 까지 루프를 돌면서 s1과 s2..

문제 백준 9084 C++ 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include #include using namespace std; int dp[10001]; int main() { int t; cin >> t; while (t > 0) { // 입력 int n; cin >> n;..

문제 백준 11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr = n * (n -1) * (n-2) * ... * (n-r+1) / r! 이지만 n과 r이 커지면 오버플로우가 발생합니다. 따라서 파스칼의 법칙을 사용하여 dp로 해결합니다. 위 그림을 보면 nCr에서 r이 0이거나, n = r일 때는 1, 나머지 경우에는 nCr = n-1Cr-1 + n-1Cr 입니다. 1C0과 1C1의 초기값을 설정해주고 dp를 이용해 nCk을 구합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 백준 11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 [i, j]에서 [i+1, j], [i][j+1], [i+1][j+1]로 이동할 수 있습니다. [i+1][j+1]은 어차피 [i+1, j], [i][j+1]를 거쳐 이동할 수 있으므로 고려하지 않아도 됩니다. (돌아서 갈 때 얻는 사탕이 무조건 크거나 같습니다.) 따라서 dp[i]j[j]에는 dp[i-1][j], dp[i][j-1] 중 더 큰 값에 map[i][j]를 더해준 값을 넣습니다. 소스 코드 1 2 3 4 5 6 ..

문제 백준 1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 해당 영역에서 가장 큰 길이를 계산해 담고 있는 dp 배열을 이용합니다. 먼저 0열과 0행에는 입력값과 똑같은 값을 넣어줍니다. 0열과 0행을 제외하고, 해당 칸의 입력이 0이라면, 어짜피 사각형의 길이는 0이 되므로 dp에 0을 넣어줍니다. 1이라면 왼쪽, 위쪽, 왼쪽 위 3가지 값을 탐색하면서 dp 값을 구합니다. dp값과 최대 길이 값을 비교하여 최댓값을 갱신합니다. 예제를 보겠습니다. square 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 dp 0 1 0 0 0 1 0 0 0 0 0행과..

문제 백준 2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 dp 배열은 (인덱스, 몇번 연속으로 마셨는지) 중에서 최댓값을 나타냅니다. 예제로 보겠습니다. 6 10 13 9 8 1 0 0 6 16 23 28 33 1 6 10 19 25 31 29 2 0 16 23 28 33 32 먼저 1번째, 6일 때 안 마시는 경우(dp[0][0])를 0, 2번 연속 마시는 경우는 없으니 0으로 초기화 해줍니다. 1번 연속 마시는 경우에는 arr[0]값인 6을 넣어줍니다. 2번째에서 안 마시는 경우는 dp[i-..

문제 백준 9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 점화식만 알면 쉽게 풀 수 있는 문제입니다. 점화식은 직관...으로 찾았습니다. 인덱스가 커지면 배열의 값이 int 범위를 초과하므로 배열을 long long 형으로 선언합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; long long dp[101]; int main() { int t; int n..