겜돌이의 개발일지

문제 백준 4811 알약 C++ 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 Top-down 방식의 dp를 이용한다. 알약을 꺼낼 때, 경우의 수는 다음과 같다. (반 개 짜리는 h, 한 개 짜리는 w로 지칭한다.) dp[w][h]는 한 개 짜리가 w, 반 개 짜리가 h만큼 있는 경우 알약을 먹을 수 있는 가짓 수를 뜻한다. 1. w != 0, h != 0인 경우 1-1. w를 먹는다. h가 한 개 늘어나고 w는 1 줄어든다. 그 후에 dp[w-1][h+1] 만큼의 경우의 수가 생긴다. 1-2. h를 먹는다. h가 ..

문제 백준 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. 상하좌우 순으로, 다음값이 현재값보다 크다면 둘 중..

문제 백준 4883 삼각 그래프 C++ 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 기본적인 DP문제이다. 각 행은 3열이고, 조건에 따라 열까지의 최소 거리를 저장하는 배열 dp에 따라 최소 거리를 갱신해준다. dp 배열의 첫 행 첫 열에는 쓰레기값을 넣어주는데, 시작 지점이 따로 있으므로 첫행첫열에서 최소 거리를 갱신하지 못하게 하기 위함이다. 소스 코드 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..

문제 백준 2240 자두나무 C++ 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전형적인 dp문제이다. 1번에서 시작한다는 문구를 놓쳐서 디버깅하는데 시간이 쪼오끔 걸렸다... (2번에서도 시작할 수 있는줄 알았음) 움직이지 않는 경우에는 첫번째에 있는 경우이므로, 그 전칸에서 바로 가져오고 1번째 칸은 1번째에서 그대로 내려오거나 / 2번째 칸에서 바꾸거나 2번째 칸은 2번째에서 그대로 내려오거나 / 1번째 칸에서 바꾸거나 각각 2가지 경우가 있으므로 이를 비교하여 더 큰 값을 취하고 dp배열에 저장해두면 ..

문제 백준 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로 한 번 붙..

문제 백준 14002 가장 긴 증가하는 부분 수열 4 C++ 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 LIS 구하기의 경우 DP로 해결하면 O(N^2)의 시간복잡도를 가집니다. N = 1000이므로 DP로도 해결가능해 DP로 풀었습니다. N이 더 커진다면 이분 탐색을 활용해야 합니다. 최장 증가 부분 수열의 경로도 출력해줘야하는데, 부모를 설정하면 경로를 쉽게 표시할 수 있습니다. 소스 코드 1 2 3 4 5 6 7 ..

문제 백준 2096 내려가기 C++ 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 Max, Min 값 등을 배열로 정리했으면 더 깔끔한 코드가 나왔을 것 같다. 메모리 초과에 유의하여 10만 크기의 배열을 선언하지않고, 전 단계 값만 저장하면서 갱신해준다. 소스 코드 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 36 37 38 39 40 #include #include using namesp..

문제 프로그래머스 42898 등굣길 C++ 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 해당 좌표가 웅덩이인지 저장하는 water배열을 선언하고, 웅덩이 좌표를 넣어줍니다. 그 이후에는 일반적인 길찾기 처럼 DP를 이용하되, 웅덩이일 경우에는 경로를 계산하지 않고 넘어갑니다. 소스 코드 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 36 #include #includ..

문제 프로그래머스 43105 정수 삼각형 C++ 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 지금까지의 경로의 합 중 최댓값을 저장해놓은 배열을 DP라고 선언합니다. DP는 다음과 같은 규칙을 따릅니다. 1. 줄의 첫 칸 일 경우 : 자신의 DP값 = 전 줄의 첫 칸의 DP값 + 자신의 값 2. 줄의 마지막 칸 일 경우 : 자신의 DP값 = 전 줄의 마지막 칸(j-1)의 DP값 + 자신의 값 3. 그 외의 경우 : 자신의 DP값 = 전 줄의 j-1, j번째 DP값 충 더 큰 값 + 자신의 값 삼각형의 값은 0이상이므로 마지막 줄인 경우에만 최댓값을 갱신해주면 됩니다. 소스 코..