성준이의 개발블로그 성준이의 개발블로그

문제 링크https://www.acmicpc.net/problem/3190문제 이해이 문제는 뱀이 벽에 부딪히거나 자기 자신과 부딪혀서 게임이 끝날 때의 이동 시간을 출력하는 문제입니다. 뱀은 처음 0,0에서 시작하고 오른쪽 방향을 바라보고 있습니다. 뱀은 매초마다 이동하는데, 몸 길이를 바라보는 방향으로 늘려 머리를 이동시킵니다. 이동하는 칸에 사과가 있다면 사과가 없어지고 몸 길이가 1길어지고 이동하는 칸에 사과가 없다면 꼬리 부분이 잘려 몸 길이가 그대로인 채로 이동하는 것과 같습니다. 방향은 시간 방향 형식으로 주어지는데 특정 시간이 지났을 때 특정 방향(오른쪽 or 왼쪽)으로 회전합니다. 방향이 “D”라면 오른쪽으로 회전합니다. 만약 오른쪽이였다면 아래를 바라보게 되고, 방향이 “L”이라면 왼쪽..

문제 링크https://www.acmicpc.net/problem/11866문제 이해이 문제는 요새푸스 순열을 출력하면 되는 문제입니다.만약에 (7,3) 요시푸스 순열이라면 가 나오게 되는데요 어떤 과정을 거쳐서 나오게 되는거냐면현재 인덱스에서 k-1을 더하고 전체 개수로 나머지 연산하여 인덱스를 구하고 그 수를 빼는 과정입니다.idx = (idx +k-1) % length 라는 공식이 나옵니다.인덱스는 0으로 시작합니다.그리고 K는 3이니 K-1 = 2므로 각 연산마다 2를 더해줍니다.(1,2,3,4,5,6,7) -> 3(0 + k-1)%7 해서 인덱스 2가 나오게 되고 인덱스 2번은 3이므로 3을 뺍니다.(1,2,4,5,6,7) -> 6(2 + 3 - 1) % 6 → 4가 나오게 되고 인덱스 4는 6..

문제 링크https://www.acmicpc.net/problem/1021문제 이해이 문제는 N이 주어지면 [1, 2, …, n-1, n]이 주어지고두번째 줄에 주어지는 숫자를 3개의 연산을 통해 빼내는 최소 횟수를 구하는 문제입니다.연산은 다음이 있습니다.첫번째 원소를 뽑아낸다. [1, 2, …, n-1, n] → [2, 3, …, n-1, n]왼쪽으로 한칸 이동시킨다. [1, 2, …, n-1, n] → [2, 3, …, n, 1]오른쪽으로 한칸 이동시킨다. [1, 2, …, n-1, n] → [n, 1, …, n-2, n-1]아이디어우선 이 문제에서 원소를 뽑아내는 것은 1번 연산밖에 없습니다.그래서 가장 최적의 2,3번 연산을 수행하여 최소 횟수로 원소를 잘 뽑아내면 되는 것입니다.최적의 2,3번..

문제 링크https://www.acmicpc.net/problem/16943문제 이해A와 B가 주어지는데 A의 숫자들을 해체하여 재조합하여 새로운 수 C를 만드는데C는 B보다 작아야 하고 최대한 크게 만들어야 합니다.C를 B보다 작게 만들수 없으면 -1을 출력하고 작게 만들 수 있으면 최대값을 출력하는 문제입니다.아이디어생각한 아이디어는 다음과 같습니다.우선 순열로 A를 재조합해서 만들 수 있는 경우의 배열을 모두 구한다.그 배열에서 filter를 사용하여 b 이하인 수들만 남긴다.앞자리가 0이 되면 안되므로 A의 길이와 같은 수들만 남긴다.배열에 뭐가 남아있으면 max(배열)로 최대값 출력하고 뭐가 없다면 -1을 출력한다.시간복잡도우선 최대는 10의 9승 자리수는 10개 입니다 이 하지만 가장 시간 복..

문제 링크https://www.acmicpc.net/problem/1527문제 이해금민수는 4와 7로만 이루어진 숫자를 의미하는데 주어지는 A이상 B이하의 수 중에 금민수가 몇 개 있는지 출력하면 된다.아이디어처음에는 그냥 A부터 B까지 전부 반복문 돌리면서 4와 7로만 이루어진 수일때 cnt+1을 해주려 하였지만 최대가 10억이기 때문에 최악의 경우 10억번 연산을 돌기 때문에 시간초과가 날 것이였습니다.하지만 금민수 배열을 미리 만들어둘 때 이 배열은 개수가 적을것이라는 생각이 들었고, 10억 아래의 금민수는 1000개 정도밖에 없었습니다.그래서 이 배열을 순회하며 A와 B사이에 있는 수라면 cnt +1을 하는 방식으로 풀기로 했습니다. 아이디어를 정리하면금민수 배열을 만든다.10을 곱하고 4를 더하..

문제 링크https://www.acmicpc.net/problem/15686문제 이해전체 치킨집에서 가게유지비용 때문에 남길 치킨집을 m개로 정했을 때 모든 집에서 치킨집까지의 거리가 최소가 되는 집을 구하고, 최소거리를 출력하는 문제입니다.집과 치킨집과의 거리는 집과 치킨집의 행과 열의 차이를 더한 것으로 |치킨집x-집x| + |치킨집y-집y| 입니다.아이디어최적의 치킨집이 뭔지 찾으려면 어떻게 해야할까 생각하다가 딱히 규칙이 보이지 않았고 전부 탐색을 해봐야겠다고 생각했습니다.그래서 치킨집의 좌표와, 집의 좌표를 저장해두고 전체 치킨집에서 m개를 뽑는 모든 경우의 수를 탐색하여 최소거리가 나오는 것을 출력하려는 아이디어를 세웠습니다.그래서 나온 아이디어는 다음과 같습니다.입력에서 집의 좌표와 치킨집의..

문제 링크https://www.acmicpc.net/problem/14891문제 이해이 문제는 톱니바퀴가 맞물려서 회전하고 다 회전했을 때의 12시 방향의 극이 어떤지에 따라 1,2,4,8을 더해서 값을 출력하는 문제입니다. 12시 방향의 극이 어떤지에 따라 값을 더하는 구성을 살펴보면1번 톱니바퀴 : N일 경우 0을 더하고, S일 경우 1을 더합니다.2번 톱니바퀴 : N일 경우 0을 더하고, S일 경우 2를 더합니다.3번 톱니바퀴 : N일 경우 0을 더하고, S일 경우 4를 더합니다.4번 톱니바퀴 : N일 경우 0을 더하고, S일 경우 8을 더합니다.톱니바퀴는 시계방향 혹은 반시계 방향으로 한칸씩 회전을 하는데맞닿아 있는 극이 서로 다르다면 맞닿은 톱니바퀴가 반대방향으로 회전하고 극이 같다면 맞닿아 있..

문제 링크https://www.acmicpc.net/problem/14499문제 이해이 문제는 주사위를 동,서,북,남 방향으로 굴렸을 때 윗면의 눈금을 출력하는 문제입니다.주사위는 처음 시작할 때 모든 면이 0입니다.굴릴때 격자가 0이라면 주사위 밑면의 눈금이 격자로 복사되고굴릴때 격자가 0이 아니면 격자의 눈금이 주사위로 복사되고 격자의 눈금은 0이 됩니다.그리고 지도의 바깥으로 나가면 아무런 동작을 하지 않습니다.아이디어처음에 제가 생각했던 아이디어는 다음과 같습니다.주사위의 윗면이 1일때 동서남북으로 굴릴때 밑면의 주사위 눈금이 뭐가 나오는지 확인하는 것입니다.상상으로는 안됐기 때문에 종이로 전개도를 그리고 접어서 확인해봤습니다…그래서 나온 결과는 다음과 같았습니다.# dice_direction =..