참외 나누기
다이아몬드 IV의견: 0
⚠️ ICT어워드 코리아 중등부 기출을 정확한 자료 없이 기억에 의존해 재구성한 문제입니다. 실제 문제와 다를 수 있으며, 서브태스크(부분 점수)가 없습니다.
참외 \(N\)개가 한 묶음으로 있다. 참외 \(k\)개짜리 묶음은 다음 규칙으로 두 묶음으로 쪼갤 수 있다.
- 첫 번째 묶음 \(a = \lceil k/3 \rceil\)
- 두 번째 묶음 \(b = k - a\)
즉 쪼개는 방법은 매번 한 가지로 정해지며, 한 번 쪼개는 데 1분이 걸린다. (\(k = 1\)인 묶음은 더 쪼갤 수 없다.) 쪼개서 생긴 여러 묶음 중 일부를 골라 합치면 그 합만큼의 개수를 만들 수 있다.
\(1\)부터 \(N\)까지의 각 정수 \(t\)에 대해, 참외 \(N\)개짜리 묶음에서 정확히 \(t\)개를 만들기 위해 필요한 최소 시간(분)을 구하라. 만들 수 없으면 \(-1\)을 출력한다.
\(1 \le N \le 250\,000\)
첫째 줄에 정수 \(N\).
\(t = 1\)부터 \(N\)까지 각 \(t\)에 대해 정확히 \(t\)를 만드는 최소 시간(분)을 공백으로 구분해 한 줄에 출력한다. 만들 수 없으면 그 자리에 \(-1\)을 출력한다.
9
2 2 1 2 2 1 2 2 0
\(9\)는 항상 \(\bigl(\lceil 9/3 \rceil,\ 9 - 3\bigr) = (3, 6)\)으로 쪼개진다. \(t = 9\)는 묶음 전체라 \(0\)분, \(t = 3\)과 \(t = 6\)은 한 번만 쪼개 해당 묶음을 가져오면 \(1\)분, \(t = 1\)은 \(6\)짜리 묶음을 다시 쪼개야 하므로 \(2\)분이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
평가 및 의견
참외 나누기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
참외 나누기