코드 낙서장

17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 확인 해시를 이용한 구현 문제입니다. 풀이 문제의 두 연산을 구분하기 위해 행, 열의 최대 길이를 미리 기록 해 둡니다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수

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(..

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제 확인 벡터의 특성과 벡터를 선택하는 조합 문제입니다. 풀이 문제에서 주의해야 할 점은 벡터의 합의 길이이므로 (0, 10), (0, -10) 벡터의 합은 (0, 0)이므로 길이는 0이 됩니다. 따라서 벡터의 합을 구할 때 단순히 sqrt((x1 - x2)^2 + (y1 - y2)^2)로 구하면 틀리게 됩니다. 전체 벡터 합을 구한 후 선택한 벡터들의 차를 이용하여 벡터의 합을 빠른 시간에 구할 수 있습니다. (x1, y1), (x2, y2) .....

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

16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 문제 확인 스택 혹은 dfs로 풀어도 되지만 간단한 로직으로 풀 수 있습니다. 풀이 문자열에서 사전 순으로 빠른 문자는 아스키 값으로 낮은 문자이므로 간단하게 대소 비교를 통해 구별할 수 있습니다. 문자열을 구간으로 나누고 해당 구간에서 가장 낮은 문자를 택해 해당 문자를 추가하고 이로 인하여 나뉘는 2개의 구간을 같은 방식으로 처리합니다. 백준 예시 STARTLINK 보면 0 ~ (N-1) 구간에서 가장 빠른 문자는 A입니다. 이로 인하여 ST / RT..

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까지 오름차순으로 이동하여 겹치는 상어는 그 순간 내보낼 수 있도록 합니다. 주의해야 할 점은 냄새와 상어의 위치를 구분지어야 같은 칸에 상어가 들어갈 수..

9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 확인 다익스트라 알고리즘을 활용하는 문제입니다. 풀이 방법은 2가지가 있으며 두 방법 모두 비슷한 결과로 나옵니다. 1번의 다익스트라 알고리즘을 수행하면서 g-h 간선을 지나는 경우를 체크하는 방법 start-g + g-h + h-dest 혹은 start-h + h-g + g-dest 가 start-dest와 값이 같은지 확인하는 방법, 3번의 다익스트라 알고리즘을 수행 결과가 비슷한 이유는 기존 다익스트라 알고리즘 계산 시 dist, graph 배열..

www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 문제 확인 게임트리 문제입니다. 풀이 가지고 갈 수 있는 돌의 개수는 1, 3, 4개 이므로 현재 플레이어가 이길 수 있는 경우의 수는 현재 남은 돌에서 x 개를 가져가서 1, 3, 4를 만들 수 없는 수의 돌을 남기는 것입니다. 따라서 2, 7, 9, 14 .. 가 되며 이는 7로 나눈 나머지가 2, 0 인 경우입니다. 코드 1 2 3 4 5 6 7 8 9 10 #include int main() { long long n; scanf("%lld", &n); if (n % 7 == 0 || n % 7 == 2) printf(..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 확인 배열 인덱스를 따라가면서 만족하는 인덱스를 찾는 방식으로 풀 수 있습니다. 스택을 활용하여 문제를 풀어도 비슷한 결과가 나옵니다. 풀이 2가지 경우로 나눕니다. 전에 입력받은 탑의 크기가 현재 탑 보다 큰 경우 : 현재 탑이 발사한 레이저 신호를 수신한 탑은 i - 1이 됩니다. 현재 탑이 작은 경우 : i - 1부터 수신 가능한 탑을 찾아 내려갑니다. i - 1 번째 탑이 발사한 레이저 신호를 어느 탑이 수신하였는가(dist[i-1])를 보고 수신..

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