코드 낙서장

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 확인 구현 문제입니다. 풀이 세로로 이동하는 경우 입력받은 배열을 전치시켜 계산하여 메모리 접근 상 더 좋은 결과를 얻을 수 있습니다. ary[i-1] , ary[i]를 비교하여 3가지 경우로 나눌 수 있습니다. ary[i-1] == ary[i] : 경사로를 놓을 수 있는 공간이 하나 늘어납니다. => count++ ary[i-1] + 1 == ary[i] : 경사로가 ary[i] 왼쪽에 필요하며 이전 경사로를 놓을 수 있는 공간이 L개 이상인 경우 이동이 가능합니다. => if(..

17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 확인 구현 문제입니다. 풀이 후에 사용할 평균값을 빠르게 구할 수 있도록 모든 원소의 총합 total, 모든 원소의 개수 cnt를 미리 구해둡니다. 밴치마크를 기록해두고 이를 이용하여 회전 시 모든 배열의 원소를 수정할 필요 없도록 합니다. 밴치마크를 처음 0번째 원소가 있는 위치 즉 북쪽 위치의 원소를 가리키는 인덱스로 둡니다. 회전을 하게 되면 밴치마크가 가리키는 인덱스가 변하게 되며 회전 방향의 반대 방향의 인덱스가 설정됩니다. 위와 같..

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 문제 확인 구현 문제입니다. 풀이 주어진 조건대로 풀면 쉽게 풀 수 있는 문제입니다. 일일이 모든 냄새의 수명을 -1씩 하면 느리므로 냄새를 뿌리면 해당 냄새의 수명을 depth + k로 기록하여 depth가 이를 넘을 경우 접근할 수 있도록 합니다. 상어를 1부터 m까지 오름차순으로 이동하여 겹치는 상어는 그 순간 내보낼 수 있도록 합니다. 주의해야 할 점은 냄새와 상어의 위치를 구분지어야 같은 칸에 상어가 들어갈 수..

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 문제 확인 경로를 합칠 수 있으면 길이가 단축되므로 경로들을 정렬해서 합칠 수 있는지 확인하는 스위핑 문제입니다. 풀이 출발지가 목적지보다 왼쪽, 낮은 수인 경우 M으로 가는 도중 처리할 수 있으므로 배열에 넣지 않습니다. 배열에는 목적지가 출발지보다 왼쪽에 있는 경우만 선택해서 담아 이를 목적지 기준으로 정렬합니다. 경로를 합칠 때 돌아갔다가 오는 길이를 줄이기 위해서는 서로 겹치는 부분이 있는 경우만 합쳐서 새 경로를 만들어 줍니다. 예를 들어 다음과 같은..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 확인 map, set을 이용해 해쉬로 풀어도 되지만 느리므로 투 포인터 알고리즘으로 풉니다. 풀이 2개의 수를 잡아서 어떠한 수를 만들 수 있는지 확인하는 방식은 O(N^2), 하나의 수를 잡고 이 수를 만들 수 있는지 확인하는 방식 또한 O(N^2)지만 전자의 경우 그 수가 배열 안에 있는지 확인해야 하는 작업이 필요하므로 더 많은 시간이 필요합니다. 투 포인터 알고리즘을 사용하기 위해 먼저 정렬을 합니다. 그 후 두 포인터를 0, n-1에 두고 현재 확인할 수를 i : 0~n-1로..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 확인 경로 탐색 문제입니다. 단순 dp로 풀 수 있지만 최대 경우의 수 dp[10][1000][1000] 보다 bfs, 가지치기가 경우의 수가 적으므로 bfs으로 풉니다. 풀이 문제에서 핵심은 벽을 부수는 경우 최단경로가 달라질 수 있다는 점입니다. 따라서 벽을 부순 횟수에 따라 방문했던 칸을 다시 방문할 수 있으므로 다음과 같이 풀 수 있습니다. 처음 방문 : 현재 벽을 부순 횟수 k를 기록합니다. n번째 방문 : 기록된..

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 문제 확인 dfs 커팅, 완전 탐색으로 풀 수 있지만 500x500 이므로 크기가 커서 효율성이 떨어지기 때문에 dfs, dp로 풀어야 합니다. 풀이 판다는 전 지역보다 옮긴 지역이 더 많은 대나무가 있어야 하므로 다음식을 항상 만족합니다. ary[ path[i][x] ][ path[i][y] ]

2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제 확인 원형 큐 자료구조 형식을 응용하는 문제입니다. 모든 짚신벌레를 관리하면 메모리 초과가 일어나며 a, b, d를 고정시키고 배열을 움직이게 되면 연산이 많아져 시간 초과가 납니다. 따라서 배열의 값 대신 a, b, d를 인덱스로 이용하여 풀어야 합니다. 풀이 문제에서 주어진 d 값을 이용해 원형 큐 배열을 만듭니다. d는 최대 10000이며 이를 넘을 시 짚신벌레는 죽기 때문에 배열을 ary[10001]로 선언합니다. 초기 배열을 [1, 0, 0, ...] 으로 초기화해주고 a, b, ..

문제 주소 : www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 확인 트리에서 dp 문제입니다. 얼리 어답터인 경우 친구는 얼리 어답터이거나 아닐 수 있지만 자신이 얼리 어답터가 아닌 경우 친구 중 한 명은 꼭 얼리 어답터이어야 함을 이용합니다. 이 말은 즉 자신의 모든 친구가 얼리 어답터가 아니라면 자신이 얼리 어답터가 돼야 함을 의미하고 반대로 모든 친구가 얼리 어답터라면 나 자신은 어답터일 필요가 없습니다. 풀이 depth 조절과 효율성을 위해..