문제 이해 단계 문제 자체는 짧고 이해도 간단한 문제. X축 하나만 존재하고 점 N에서 점 K까지 가는데 총 3가지 방법이 존재한다. 1. 2 * N칸 이동 -> 시간소모 = 0초 2. +1칸 이동 -> 시간소모 = 1초 3. -1칸 이동 -> 시간 소모 = 1초 이 세 가지 방법을 이용하여, 점 N에서 점 K까지 가는 최소 시간을 찾는 문제이다. 문제 접근 단계 처음에는 최소시간을 찾는 것이기 때문에 그리디 문제인 줄 알았다. 하지만 그리디 문제의 조건은 매 순간마다의 최적의 답이 문제의 답이 되어야 한다. 이 문제에서는 나중에 분석한 답이 더 최소 시간 일수도 있기 때문에 그리디로 풀기엔 적합하지 않다. 그래서 x축에서 한 점을 기준으로 양쪽을 탐색하여 K를 찾는 BFS 방식을 사용하기로 했다. 다른..

문제 이해 단계 위 문제는 힌트를 보면 이해하기가 더 쉽다. ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO ....... ...O... ....O.. ....... OO..... OO..... 이를 요약한다면 0초 - 일부 칸 폭탄 설치(초기상태) 1초 - 행동 X 2초 - 폭탄 없는 칸에 전부 폭탄 설치 3초 - 행동 X(0초 때 설치해 뒀던 폭탄 터짐) 이후 2초, 3초 행동 반복 이 말은 폭탄이 터져 그 주..

문제 이해 단계 문제 이해 자체는 간단하다. N대의 크레인이 있고, 각 크레인마다 무게제한이 존재한다. 이때 박스 K개가 주어지고, 각 크레인마다 하나씩 옮기는 데 걸리는 시간이 1분이다. 이 때, 총 걸리는 시간의 최솟값을 구하는 문제이다. 문제 접근 단계 포인트는 두 가지로 볼 수 있을 것 같다. Point 1. 크레인 무게 제한 각자 들 수 있는 박스를 생각했을 때, 무게 제한이 클수록 들 수 있는 박스가 많아진다. 만약 무게 제한이 5와 3인 크레인이 있다면 3인 크레인은 1,2,3 밖에 못 들지만, 5인 크레인은 1,2,3,4,5까지 들 수 있다. 여기서 중요한 점은 5 크레인은 3 크레인의 박스를 들 수 있지만 그 반대는 안된다는 것이다. 5인 크레인은 3인 크레인에게 영향을 줄 수 있다. 그..

문제 이해 단계 문제 이해가 너무 힘들어서 인터넷을 참고하여 문제를 이해하였다. 한마디로 말하면 집중국은 길이로 나타난다. 만약 1개의 집중국으로 위치가 1,7인 센서를 수신하려면 수신 가능 영역은 6(7-1), 길이 같은 느낌으로 해석하면 된다. 즉, K개의 줄로 각 위치에 있는 센서를 연결하는 최소의 수를 구하는 문제이다. 이해를 위해 예제를 그림으로 알아보면 이런 식으로 나타난다. 2개의 집중국을 사용한 수신 가능 영역의 길이의 최솟값이다. 문제 접근 단계 이 문제는 결국 길이를 최소화하기 위해 K개의 그룹으로 나누는 방법을 따지는 문제이다. 길이는 해당 그룹에서 최댓값 - 최솟값으로 나타난다. 길이를 최소화하기 위해서는 당연히 값이 비슷한 센서를 빼야 한다. 따라서 오름차순 또는 내림차순으로 정렬..

문제 이해 단계 https://www.acmicpc.net/problem/20365 문제 자체는 이해하기 쉽다. 이웃한 번호까지 한 번에 같은 색으로 칠한다. 예를 들어 1번 7번을 선택하면, 1~7번까지 모두 같은 색으로 칠해진다는 뜻이다. 이런 식으로 했을 때, 모든 번호를 원하는 색으로 칠하는 최소 횟수를 구하라는 것이 문제이다. 문제 접근 단계 어떻게 하면 최소로 할 수 있을까? 라고 생각을 하다가 예시에 나와있는 BBRBRBBR로 생각을 했다. 첫 번째로 B로 최대한 많은 색을 칠한다.(1~7번) 이후 사이사이 박혀있는 R을 칠하는데 이웃한 것이 있다면 같은 횟수로 간주한다. 하지만 여기서는 R이 다들 떨어져 있기 때문에, 하나씩 간주했다. 그래서 (1~7번), (3번), (5번), (8번) 총..

문제 이해 단계 문제 자체는 굉장히 단순하다. 운동을 2개씩 짝지어하는데, 하나가 남을 경우 그건 따로 진행한다. 이런 식으로 진행하는데 2개의 숫자의 합과 남은 하나의 숫자를 최소 값으로 하는 수를 찾는 것이다. 문제 접근 단계 이 문제의 포인트는 주어진 운동의 수가 홀수인가 짝수 인가로 나뉜다. 운동 수가 짝수라면, 무조건 두 수의 합이 최소가 되는 값을 찾아야 한다. 하지만 홀수라면 무조건 하나가 남게 되기 때문에, 최솟값을 산출하기 위해 남을 1개의 수를 찾아야 한다. 일단 최솟값이 되기 위한 방법을 생각해 보자. 당연히 (높은 수) + (낮은 수)를 하는 것이 값을 최소화하는 방법이다. (가장 높은 수 + 가장 낮은 수), (그다음 높은 수 + 그다음 낮은 수)... 이런 식으로 모두 계산했을 ..

문제 이해 단계 문제는 아주 단순하다. AAAA와 BB 두 개의 타일을 가지고 있는데, 주어진 X를 타일로 대체하는 것이다. 같은 경우는 구분하지 않고 그대로 출력하는 것인데, 이건 입력 예제를 보다 보면 바로 이해가 되는 것이기 때문에 자세히 다루지는 않겠다. 문제 접근 단계 이 알고리즘을 푸는 데에는 3가지 포인트가 있다. 1. "."을 기준으로 문자열 X를 나누는 구현 2. AAAA와 BB 타일을 배치하는 방법 구현 3. "-1"을 도출하는 방법 구현 Point 1 . 을 기준으로 문자열을 구분해야 하므로 문자열을 모두 받아 글자 하나하나씩 읽어가는 방식을 선택했다. "X" 일 때와 "." 일 때를 구분하여 행동을 다르게 하였다. "X"일 때는 문자열을 순차적으로 읽다가 "."을 만나면 그때까지의 ..

문제 이해 단계 https://www.acmicpc.net/problem/5639 문제 자체는 자료구조 트리의 정석적인 문제이다. 전위 순회, 중위 순회, 후위 순회를 잘 알고 있나에 관한 문제이다. 간단히 말해서, 전위 순회로 입력이 들어온 트리 구조를 후위 순회로 출력해라는 뜻이다. 문제 자체는 굉장히 심플하다. 하나, 완전 이진트리는 아니기 때문에 여러 가지 디테일이 필요했다. 문제 접근 단계 위 문제를 풀기 위해서는 여러 가지 전위 순회로 들어오는 입력의 특징을 잘 잡아서 해결해야 한다. 일단 이진트리의 특성상 하나의 자식 노드는 다른 서브 트리의 부모 노드가 될 수 있다. 그렇기 때문에 이를 재귀함수로 서브 트리를 호출해 주면서 풀어줘야 한다는 생각을 했다. 일단 전위 순회에서 한 트리를 구성할..