CSES

CSES.key

1.56MB

Increasing Array

단조 증가 수열로 만들기 위한 최소의 시행 횟수를 구하라는 문제이다.
이 문제에서 시행은 1 증가시키는 시행을 뜻한다.

단조 증가 수열은 모든 \(i\)에 대해 \(a_i \leq a_{i+1}\;(0\leq i< n)\)가 만족하면 충분하다.

\(a_i > a_{i+1}\;(0\leq i< n)\)일 때, 부분적인 최소의 시행 횟수는 \(a_{i+1}-a_i\)임이 자명하다.
그리고, \(a_j \leq a_i\; (0\leq j < i<n)\)를 만족하던 모든 \(a_j\)는 \(a_i\)가 증가해도 식을 만족시키므로 아무 문제가 없다. 따라서 다음의 알고리즘은 정당하다. ∎

Permutations

Constructive한 문제이다. 필자와 다른 풀이일 가능성이 충분히 있다.

 

\(n\)의 값에 따라 3가지 케이스로 분류해보자.
\(i.\;n=1\)
답 : \(1\)

 

\(ii.\;n\in\{2,3\}\)
답 : \(\mathrm{NO\; SOLUTION}\)

 

\(iii.\;n \geq 4\)
답 : \(\left \lfloor \frac{n+1}{2} \right \rfloor,\;n,\;1,\;n-1,\;2,\;\cdots\)의 방식으로 나열된 수열

 

\(|\left \lfloor \frac{n+1}{2} \right \rfloor -n| \leq 1\)인 \(n\)의 범위?
= \(|n-1| \leq 2\)인 \(n\)의 범위?
\(\therefore n\leq 3\; \mathrm{or}\; -1\leq n.\) 따라서 \(n \geq 4\)라는 범위는 합리적이다.

다만, \(n\)의 기우성에 따라 수열의 끝이 달라질 수 있는 점을 고려해야 한다.
예시를 통해 확인해보자.

\(n=4\)
\(2-4-1-3-\not{2}\)

\(n=5\)
\(3-5-1-4-2\)

마지막에 \(f\)와 \(b\)의 값이 똑같아지는 순간 때문에 예외가 발생했던 것이다.
따라서 if문만 추가하면 맞게 된다.

**********Carbon에서 기존에 지원되던 폰트가 사라졌어요ㅠ**********

Number Spiral

노가다로 대략 패턴을 찾아주면 됩니다. 바로 윗 문제 Permutation처럼 규칙성을 찾아줘야 하는 Ad-hoc한 문제입니다.

격자, 삼각수, 제곱수 등...을 고려하면서 풀어봅시다.

푼지 1달정도 되서 기억이 안 나기 때문에 풀이 필요하신 분 댓글 달아주시면 그때부터 적어보도록 할게요...