칼질을 최소로 하는 방법 알고리즘

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	453	209	187	49.471%

목차 Show

티스토리 뷰

문제

제이크는 레이니콘으로부터 긴 모양의 케이크를 선물 받았습니다.

케이크 위에는 N개의 과일 조각이 올려져 있는데 케이크 위에는 딸기 N/2개와 키위 N/2개가 일정한 간격을 두고 일렬로 올려져 있습니다. 여기서 N은 4의 배수입니다.

제이크는 케이크를 핀과 올려진 과일의 종류를 포함하여 케이크를 정확히 절반씩 먹기 위해 받은 케이크를 잘라서 나누어 가지려고 합니다. 이때 제이크가 받은 딸기가 N/4개여야 하며 키위도 N/4개 있어야 합니다. 핀도 제이크와 같은 개수의 딸기와 키위를 받아야 합니다.

제이크와 핀은 케이크를 자르기 귀찮으므로 그 횟수를 최소화하고자 합니다. 핀과 제이크가 똑같이 나누어 먹기 위해 케이크를 잘라야 하는 최소 횟수와 방법을 알려주세요.

입력

첫 번째 줄에는 케이크 위에 있는 과일의 개수 N (4 ≤ N ≤ 200,000) 이 주어집니다.

두 번째 줄에는 케이크의 정보가 담긴 길이가 N인 문자열이 주어집니다. i번째 문자가 's'이면 i번째 칸에는 딸기가 'k'이면 키위가 올려져 있음을 의미합니다.

출력

첫 번째 줄에 최소 횟수 k (1 ≤ k ≤ N - 1) 를 출력합니다.

두 번째 줄에는 k개의 정수 c1, c2, ..., ck (1 ≤ c1 < c2 < ... < ck ≤ N - 1) 를 출력합니다. 여기서 ci는 ci 번째 과일이 있는 곳과 ci +1번째 과일이 있는 곳 사이를 자른다는 의미입니다.

자르는 방법이 여러 개인 경우 그 중 하나만 출력합니다.

c1 = 1번째 과일과 2번째 과일 사이를 자르고 c2 = 5번째 과일과 6번째 과일 사이를 잘라서 총 k = 2 번의 칼질로 케이크를 공평하게 나눌 수 있습니다.

[Programmers] 길 찾기 게임

이진트리의 순회 문제이다. 이 문제는 이진트리의 노드들이 주어지고 전위순회(루트->좌->우), 후위순회(좌->우->루트)를 구하는 문제였다. 보통의 문제들과 다른점은 간선을 그리는 것이 주요한 문제였다. 따라서 두가지 과정을 거쳐 간선을 그려보았다. 일단 첫번째로 모든 노드들을 y로 내림차순, y가 같다며 x로 오름차순이 되도록 정렬을 하였다. 그 후에 Node라는 클래스를 만들어 left, right를 Node의 형으로 멤버변수(포인터의 개념)를 주고, 정렬된 노드들을 x값을 비교하여 left,right에 할당하며 연결해주었다. 이것을 완료한 후에는 재귀를 이용하여 간단하게 전위순회, 후위순회를 하여 풀었다. 문제의 우선순위, 즉 이문제에서는 간선을 그리는것이 최우선목표인데 그것을 해결하는 것이 중요한..