jwoo101010   1년 전

문제
원더랜드의 월스트리트에서 우리는 n개의 은행을 가지고 있으며, 10,000 > n > 0입니다. 각 은행에는 정확히 두 개의 이웃이 있습니다. 왼쪽(L)과 오른쪽(R) 이웃입니다. 첫 번째 은행의 왼쪽 이웃은 마지막 은행이고, 마지막 은행의 오른쪽 이웃은 첫 번째 은행입니다. 각 은행 i(n>i≥0)는 자본 ki가 32000>ki>-32000입니다. 모든 은행의 전체 자본은 양수인 것으로 알려져 있습니다. 은행 i의 자본 ki가 음수일 때마다 은행 요정은 마법의 움직임을 수행하고 자본을 양수로 바꿀 수 있습니다. 예를 들어, ki=-7이면 마법의 움직임 후에 ki=7이 됩니다. 불행히도 마법의 움직임은 은행 i의 두 이웃에게 영향을 미칩니다. 각각은 은행 i의 자본의 절대값으로 자본이 감소합니다. 예를 들어 은행 L의 자본이 kL=5이고 은행 R의 자본이 kR=11이면 마법의 움직임 후에 kL=-2이고 kR=4입니다.

은행 요정이 모든 은행의 자본금을 0보다 크거나 같게 만들기 위해 해야 하는 최소한의 마법 이동 횟수는?

입력
첫 번째 입력 줄에는 은행의 수 n이 있습니다. 두 번째 입력 줄에는 모든 은행의 자본금 ki(n>i≥0)이 원더랜드의 월스트리트에서 발견된 순서대로 있습니다. 각 자본금은 다음 자본금과 단일 공백으로 구분되지만 마지막 자본금의 경우 줄 바꿈 문자 바로 뒤에 있습니다.

출력

출력에는 최소 마법 이동 횟수 값이 있는 단일 줄이 포함됩니다.

qkrwpdnr   1년 전

오 감사합니다 한 번 풀어봐야겠네요!

jwoo101010   1년 전

참고로 이 글은 구글 번역기를 이용해 번역하였으며, 번역 의도는 제가 한번 풀어보고 싶어서 입니다!

jwoo101010   1년 전

1986년 국제수학올림피아드(IMO)에서 3번문제로 출제되것을 일반화한 것

정리

원순열 길이 n의 은행이 있는데, ki가 음수면 ki-1, ki+1에 ki만큼 뺀다. 이를 행동 A라 한다.

이때, 모든 ki의 값이 양수가 되는 최소한의 행동 A 하는 경우를 출력하시오.

=> BFS 문제

INP

4
1 -2 -1 3

1. -2에 행동
-1 2 -3 3

2. -3에 행동
-1 -1 3 -3

3. -3에 행동
-4 -1 0 3

4. -4에 행동
4 -5 0 -1

5. -5에 행동
-1 5 -5 -1

6. -1에 행동
1 5 -4 1

7. 1에 행동

...

=> 요정의 움직임은 순서에 상관없다(힌트는 여기까지)

원순열 길이 n의 은행이 있는데, ki가 음수면 ki-1, ki+1에 ki만큼 뺀다. 이를 행동 A라 한다.

이때, 모든 ki의 값이 양수가 되는 최소한의 행동 A 하는 경우를 출력하시오.

=> BFS 문제

INP

4

1 -2 -1 3

1. -2에 행동

-1 2 -3 3

2. -3에 행동

-1 -1 3 -3

3. -3에 행동

-4 -1 0 3


...

=>


OUT

9

kjk9704   1년 전

번역 감사합니다!

복습 차원에서 다시 이 문제를 보고 있었습니다!

댓글을 작성하려면 로그인해야 합니다.