겜돌이의 개발일지

문제 백준 2981 검문 C++ 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 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 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #include #include #include using namespace std; // 유클리드 호제법 int GCD(int a, int b) { if (a % b == 0..

문제 백준 14226 이모티콘 C++ 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 방문 체크를 2차원 배열로 해주는 색다른 문제였습니다. 할 수 있는 행동은 3가지입니다. 1. 화면에 있는 이모티콘 개수만큼 클립보드에 저장하기 2. 클립보드에 있는 이모티콘 개수만큼 화면에 붙여 넣기 3. 화면에 있는 이모티콘 1개 삭제하기 bfs를 돌면서 이모티콘 개수가 일치하지 않을 때 다음 3개에 행동을 모두 queue에 push 해 줍니다. 방문 체크는 [화면 이모티콘 개수][클립보드 이모티콘 개수]로 해줍니다. ..

문제 백준 2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 먼저 LIS (최장 증가 부분 수열)을 구합니다. LIS에 해당하지 않은 원소를 옮겨주면 되므로 n-LIS가 답이 됩니다. 소스 코드 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 #include #include #include using namespace std; int dp[201]; int main() {..

문제 백준 2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 두 포인터를 사용합니다. 먼저 입력을 받아 오름차순으로 정렬합니다. 합이 0에 가까워져야 하므로, 합이 양수일 때는 right를 왼쪽으로 옮겨 합을 감소시키고 합이 음수일 때는 left를 오른쪽으로 이동시켜 합을 증가시킵니다. 합의 절댓값이 최솟값보다 작다면 갱신해주고 target에 저장합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

문제 백준 15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹을 통해 폐업하지 않을 치킨집을 선정합니다. M개만큼 선정했다면, 브루트 포스를 통해 최소 거리를 갱신해줍니다. 소스 코드 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..

문제 백준 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..

문제 백준 5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치와 이동 횟수를 저장하는 queue를 선언합니다. 위로 올라갈 수 있을 때, 아래로 내려갈 수 있을 때 queue에 push 해주며 bfs를 실행합니다. 현재 위치가 G와 같다면 이동 횟수를 출력합니다. 소스 코드 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 41 42 43 #include..

문제 백준 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행과..

문제 백준 3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77..