[백준] 치킨 TOP N : 11582번 - Python

https://www.acmicpc.net/problem/11582

11582번: 치킨 TOP N

 

 

 

문제를 풀면서 몰랐던 개념

 

- 분할 정복 알고리즘

 

출처: 위키피디아

 

풀고자 하는 어려운 문제를 쪼갠 후, 쪼갠 문제를 합치는 것을 분할 정복(Divide and Conquer)이라고 한다.

 

 

 

문제의 접근 방법

 

 

이 문제에서는 N과 K값 모두 2의 거듭제곱 꼴이므로 위와 같은 규칙이 성립될 수 있다.

 

 

 

내가 막혔던 부분

 

인덱스 슬라이싱으로 끊어서 저장할 생각(한계) -> for문에서 증가치를 설정해주어서 그 규칙에 맞게 반복적인 작업을 수행하도록 설정

 

 

 

문제 풀이 방법

 

(1) 치킨집의 개수 N개 입력 받기

(2) N개의 치킨집의 맛의 수치들 입력 받아 리스트에 저장

(3) 정렬을 진행중인 회원들의 수 k명 입력 받기

(4) 위 그림처럼 index 변수를 하나 선언해서 N // k 값을 넣어주기

(5) 최종 값을 넣을 빈 리스트 arr 선언

(6) 0부터 N까지, index 값 만큼의 증가치를 설정해준 for문을 돌리기 (ex) N = 8, k = 2라면 index = 4 ----> 리스트 원소를 4개씩 끊어서 저장 + 총 2번의 반복문 실행

(7) arr에 치킨집 맛의 수치들이 저장되어 있는 리스트 c의 원소들을 i부터 i+index 값까지 잘라서 저장해주기

(8) 이를 오름차순으로 정렬해주기

(9) 중첩 반복문을 구현해서 위의 과정을 통해 arr에 저장되어 있는 값들을 같은 줄에 공백을 두고 하나씩 출력하기

 

 

 

소스코드

N = int(input())
c = list(map(int, input().split()))
k = int(input())

index = N // k
arr = []

for i in range(0,N,index):
    arr = c[i:i+index]
    arr.sort()
    for j in arr:
        print(j, end=' ')