STUDY

초콜릿 뺏어 먹기 문제 연두는 $N$개의 통에 초콜릿을 담아서, 초콜릿의 개수가 오름차순이 되도록 일렬로 배열해 놓는다. 즉, ($1$번째 통의 초콜릿의 개수) $\le$ ($2$번째 통의 초콜릿의 개수) $\le \dots \le$ ($N$번째 통의 초콜릿의 개수)이다. 효원이는 매일 조금씩 연두의 초콜릿을 몰래 뺏어 먹을 계획을 세우는 중이다. 연두는 매우 눈치가 없기 때문에, 하루에 한 번 다음의 전략을 사용해서 초콜릿을 먹는다면 절대 눈치채지 못할 것이다. $K

봄버맨 2 문제 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다. 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이..

표 정렬 문제 영선이는 N행 M열로 이루어진 표를 가지고 있다. 행은 위에서부터 아래로 0번부터 N-1번까지, 열은 왼쪽에서 오른쪽으로 0번부터 M-1번까지 번호가 매겨져 있다. 표의 각 칸에는 양의 정수가 하나 쓰여 있으며, 표에 포함되어 있는 수는 1부터 N*M까지로 이루어진 순열을 이룬다. 즉, 각각의 수는 표에 한 번씩 등장한다. 표가 주어졌을 때, 행 우선 순서를 이용해 만든 수열을 값 수열이라고 한다. 영선이는 두 가지 방법을 표를 수정할 수 있는데, 임의의 두 행을 서로 위치를 바꾸거나, 두 열의 위치를 바꾸는 것이다. 표가 주어졌을 때, 값 수열을 오름차순으로 만들 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의..

회문은 회문아니야!! 문제 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindrom (독일어, 덴마크어) palindromi (핀란드어) palíndromo (스페인어, 포르투갈어) palindromo (이탈리아어, 에스페란토어) палиндром (러시아어) قلب مستو (아랍어) 뭔가 이상한 점이 보이지 않는가? 그 어떤 언어에서도 팰린드롬을 뜻하는 단어는 팰린드롬이 아니다! 많은 사람들이 추구하는 “대칭..

k개의 부분 배열 문제 $N$개의 서로 다른 정수를 가진 배열 $A$가 주어진다. 당신은 어제 공격력이 양의 정수 $k$인 칼을 받았다. 이 칼이 있으면 배열에 아래와 같은 연산을 적용할 수 있다. 배열을 $k$개의 조각으로 자른다. $k$개의 조각을 원하는 순서대로 재배열한다. 재배열한 순서대로 조각들을 다시 합친다. 당신은 배열 $A$에 이 연산을 원하는 횟수만큼 적용하여 (한 번도 적용하지 않아도 괜찮다) 오름차순으로 정렬하려고 한다. $k$의 값에 따라 이 연산을 적절히 적용하면 $A$를 정렬하는 것이 가능할 수도 있고, 연산을 어떻게 잘 적용해도 정렬할 수 있는 방법이 없을 수도 있다. 이 때, 배열 $A$를 정렬할 수 있는 가장 작은 양의 정수 $k$의 값을 구하는 프로그램을 작성하자. 입력 ..