문제 풀이

문제 설명이 잘 이해가 안됐었다.

이 부분이 무슨말인지 잘 몰라서 예제를 보고 대충 짐작을 해서 풀었다.
그냥 잘 배치해서 모두 강화를 눌러도 강화의 영향을 제일 적게(시계 방향으로 제일 적게 퍼지게)
즉 중복이 많게 만들어란 말이었다.

중복이 가장 많게 만드려면 가장 강화력이높은 아이템부터 내림차순으로 배치를 하면된다.

예를들어,
강화력이 5, 3, 3, 1, 0, 0, 0, 0인 아이템이 8개가있다고 하면
내림차순으로 배치를 했으니 아래와 같이 괄호 친 부분까지만 강화 될 것이다.
[5, 3, 3, 1, 0], 0, 0, 0

내림차순이 아니고 무작위로 배치 된다면 아래와 같이 모두 강화가 될 것이다.
[3, 3, 0, 5, 1, 0 ,0 ,0]

그러므로 내림차순으로 정렬하는게 우선이다. 그 다음, 차례대로 확인하면서 몇번째 인덱스까지 강화가 되는지 확인한다.

for(int i= 0;i<list.size();i++)
            {
                if(list.get(i) ==0)
                    continue;
                if(i +list.get(i)-1> ans)
                    ans = i+list.get(i)-1;
            }

현재 확인하고 있는 아이템이 몇번째 인덱스까지 강화하는지 확인, 그 인덱스가 이전까지 확인했던 인덱스보다 크다면 갱신해주면 된다.

몇가지 예외 상황으로, 아이템이 모두 0일때 내 코드에서는 1을 출력하므로 예외를 따로 처리해주고
ans+1이 list의 총 개수보다 크다면 그냥 list.size()를 출력해주면된다.

문제 링크

boj/21599

소스코드

PS/21599.java

    import java.io.*;
    import java.util.*;

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        public static void main(String[] args) throws IOException {
            List<Integer> list = new ArrayList<>();
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++)
            {
                int a = Integer.parseInt(st.nextToken());
                list.add(a);
            }
            Collections.sort(list,Comparator.reverseOrder());
            int ans =0;
            for(int i= 0;i<list.size();i++)
            {
                if(list.get(i) ==0)
                    continue;
                if(i +list.get(i)-1> ans)
                    ans = i+list.get(i)-1;
            }
            if(list.get(0) == 0)
                bw.write("0");
            else {
                if(ans+1 > list.size())
                    bw.write(Integer.toString(list.size()));
                else
                bw.write(Integer.toString(ans + 1));
            }
            bw.flush();
        }
    }