https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 아이디어 1. 미세먼지를 확산시킨다 2. 공기청정기가 돌아간다 3. T번만큼 반복한다 일단 공기청정기를 반시계, 시계 방향으로 돌리는 법을 생각해야 했다. 공기청정기 돌리기 공기청정기의 머리 쪽은 반시계 방향, 몸통 쪽은 시계방향이다. 이렇게 둘로 나눠서 구현했다. 벽을 만날 때까지 반복해야 하니 방향이 필요하다 어느 방향으로 벽을 만날 때까지 나아갈 것인지 int dx[4] = {-1,0,1,..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 나에게는 정말 어려웠던 문제다 1시간 정도 고민하고 감도 잡히질 않아 답을 보았다. 풀이 배열 두 개를 만든다. 원본 배열, 테이블이다. int arr[1005]; int dp[1005]; 답에서는 한 번씩 다 돌아가면서 체크하는 방식을 알려줬다. 그림으로 설명해보겠다 이중 for문을 사용하여 i에 대하여 나보다 작은 수이면 더하고 본다..

첫 번째 아이디어 일단 기본적인 재귀 형태로 풀려고 시도했다. 당연히 안될 걸 알고 있었지만 일단 시도 했으며 결과는 당연히 메모리 초과 CODE //Moo 게임 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } //횟수 int n; int tot = 0; bool isFine = false; void isMoo(bool m2o){ //true = m, false = o if(m2o && tot == n){ cout n; moo(n/2); return 0; } 이렇게 해본 후 문제점이 뭔지를 찾아 나갔다. 1. 재귀를 몇번 반복해야 하는 가를 알려줘야 한다. 2. 그저 ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 시행 착오 최근에 다이나믹 프로그래밍 문제를 풀때 테이블이나 재귀식이 새각나지 않는 다면 브루트 포스 또는 모든 것을 다 검사하는 방식으로 코드를 짜보고 거기서 추가 적으로 재귀를 짜라는 식의 설명을 들은 적이 있다. 그리하여 나는 일단 DFS를 사용하여 모든 경우의 수를 다 구하였으며, 결과는 시간 초과 였으며 당연한 결과라 생각해 다이내믹 프로그래밍으로 짜보려고 노력했다. CODE #include using namespace std; void init(){ ios_..

요약 1. 3으로 나누어 떨어지면 3으로 나누거나 2. 2로 나누어 떨어지면 2로 나누거나 3. 1을 빼거나 해서 4. 어떻게 해야 가장 빨리, 입력받은 N을 1로 만들 수 있는가? 아이디어 들어가기에 앞서 나의 첫 다이나믹 프로그래밍 문제이다. 답을 보고 풀었다. 강의에서는 먼저 테이블을 정의한다음 점화식을 찾았다. 테이블 정의 이 문제의 테이블은 D[i] = i 각 숫자에 대응되는 인덱스를 테이블로 만들 수 있을 것 같다 점화식 d[12] = d[12/4], d[12/2], d[12-1] d[3] = d[3/3], d[3-1] d[6] = d[6/3], d[6/2], d[6-1] d[11] = d[11-1] 이런식으로 점화식을 만들 수 있을 것 같다. 하지만 나 혼자 풀어 볼 때 무조건 재귀를 쓰겠지..

https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 요약 1. 현재 나의 위치와 탈출가능한 위치가 있다 2. 벽을 딱 한번 부술 수 있다. 벽을 부수고 최단 경로를 구하는 것 아이디어 예전에 비슷한 문제를 풀었던 적이 있다. 벽을 부순 상태일 때의 배열을 따로 만드는 방법으로 풀었던 기억이 있다. 그것과 비슷하게 dist [n][m][2]라는 배열을 만들고 dist[a][b][0] // 벽을 부수지 않은 상태 dist[a][b][..

요약 1. 국어는 내림차순 2. 국어점수각 같다면 영어는 오름차순 3. 국, 영이 같다면 수학은 내림차순 4. 모두 같다면 이름은 사전순 문제를 풀며 솔직히 어려운 문제는 아니었다 정말 쉬운 문제 였다, 그런데도 글을 쓰는 이유는 답을 맞추고 다른 사람의 코드를 보는데 정말 창의 적인 아이디어를 보았기 때문이다. 이걸 글로 쓰지 않으면 바보 라는 생각이 들어 내 손이 저절로 움직였다. 그럼 풀이를 시작하겠다. 처음 나의 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n; bool cmp(const tuple &a, const tuple &b){ int a..

요약 카드 N장을 가지고 있다.가장 많이 가지고 있는 카드의 쓰여 있는 숫자를 출력 하자 CODE #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n; long long arr[100'001]; int main() { init(); cin >> n; for(int i =0; i > arr[i]; sort(arr, arr+n); long long mxval = -(1ll mxcnt) mxval = arr[n-1]; cout

요약 바이러스가 연구실에 퍼진다 무조건 벽을 3개 세워서 최대 안전영역을 확보하는 것 아이디어 벽을 세울 수 있는 모든 경우의 수를 계산한다. 최대한 적은 계산을 하기 위해 조합을 사용한다. 즉 입력받으며 바이러스를 저장, 빈칸도 따로따로 저장한다. 그리고 조합을 사용해야 하므로 do while에 next_permutation을 사용한다. 이제 각각 벽을 세울 수 있는 곳에 벽을 세우고 난 후 바이러스를 전파 시킨 다음 안전영역을 계산한다. CODE #include #define X first #define Y second using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, ..

요약 판을 기울이며 빨간 구슬을 구멍으로 탈출시켜야 한다 그런데 파란 구슬도 동시에 움직이며 파란 구슬이 구멍으로 탈출하면 실패 동시에 나와도 실패 위의 문제 구문에서 중요한 문장이 있다면 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지이다. 구슬이 벽에 닿았을 때 기울이는 것을 멈춘다. 즉 끝까지 간다 라는 말이다. 중간에 멈추는 것이 없다. 첫 아이디어 먼저 bfs, dfs 사용을 생각했다. bfs를 사용하면 현재 갈 수 있는 방향으로 끝까지 간다음 visit 배열에 시간을 저장하는 식으로 하려고 했으나 파란 구슬까지 함께 어떻게 같이 동시에 움직여야 할지 감이 오지 않았다. 또 파란 구슬과 빨간 구슬이 겹쳤을 때, 이런 상황을 대체 어떻게 처리해야 할지 감이 오지 않았다. 그래서..