백준 24337 JAVA

문제 유형

• 그리디

문제 접근

• 답
  • 최대한 작은 건물 배열
• 주어지는 정보
  • 건물 개수 : 최대 100,000 (N)
  • 양 옆에서 보이는 건물의 개수 : 최대 100,000 (a, b)
• 정보 정리
  • 최대 연산은 N^2 미만이어야한다
    • N^2 = 10,000,000,000
    • ⇒ 완전 탐색 X(시뮬레이션, BFS, DFS 등은 사용못할 가능성이 큼)
  • 남는 예상 후보
    • DP
      • No
      • 문제와 DP간의 연관 관계를 찾을 수 없음
    • 이분 탐색
      • 가능은 할 것 같음
        • 배열을 각각 반으로 재귀적으로 나눠서 값을 채워넣는 방법을 예상함
      • 하지만 적합하지 않음
        • 값을 찾는 알고리즘이므로, 배열을 만드는 것과는 별 상관이 없음
    • 그리디
      • 적합
        • 최대한 적은 높이의 빌딩을 채워나가야한다.
        • 높이 1부터 시작하여 빌딩을 채워나갈 수 있을 것으로 예상된다.
• 풀이
  • List<Integer> BuildList = new LinkedList<>();
    • 1~a-1 까지 값을 순차적으로 삽입
    • Math.max(a,b)값을 삽입
    • b-1~1 까지 값을 순차적으로 삽입
    • N 크기를 만족하지 않는다면?
      • 1을 제일 왼쪽에 넣어야한다.
        • index 0에서부터 1을 N 크기를 만족할때 까지 삽입
        • 예외
          • a=1일 시, 1을 제일 왼쪽부터 넣으면 a=2가 되므로 모순 발생
            • index 1에서부터 1을 N 크기 만족할때까지 삽입

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

class Main {
    static int N,a,b;
    static List<Integer> map = new LinkedList<>();
    
    public static boolean Resolve()
    {
        if(a+b > N+1)
        {
            return false;
        }

        for(int i = 1; i<a; i++)
        {
            map.add(i);
        }

        map.add(Math.max(a,b));

        for(int i = b-1; i>=1; i--)
        {
            map.add(i);
        }


        while(a==1 && map.size() < N)
        {
            map.add(1,1);
        }

        while(a!=0 && map.size() < N)
        {
            map.add(0,1);
        }

        return map.size() == N;
    }
    

    
    public static void Print()
    {   
        StringBuilder sb = new StringBuilder();
		for (int n: map)
			sb.append(n).append(' ');
        System.out.println(sb);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        

        if(Resolve())
        {
            Print();
        }
        else
        {
            System.out.println(-1);
        }
    }
}