Jenikeju

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다. 

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다. 

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오. 

import Foundation

var input = readLine()!.split(separator: " ").map({Int(String($0))!})
var useList = readLine()!.split(separator: " ").map({Int(String($0))!})

var plug = Array(repeating: 0, count: input[0])
var index = input[1]
var count = 0



while !useList.isEmpty {
    
    var use = useList.removeFirst()

    if plug.contains(use) {
        continue
    } else if plug.contains(0) {
        for index in 0..<plug.count {
            if plug[index] == 0 {
                plug[index] = use
                break
            }
        }
    } else {
        var indexArr = [Int]()
        
        for item in plug {
            for i in 0..<useList.count {
                if useList[i] == item {
                    indexArr.append(i)
                    break
                }
                if i == useList.count - 1 {
                    indexArr.append(-1)
                }
            }
        }
        
        var max = indexArr.max()
        if useList.isEmpty {
            count += 1
        } else {
            if indexArr.contains(-1) {
                for (index, num) in indexArr.enumerated() {
                    
                    if num == -1 {
                        plug[index] = use
                        count += 1
                        break
                    }
                }
            } else {
                for (index, num) in indexArr.enumerated() {
                    
                    if num == max {
                        plug[index] = use
                        count += 1
                        break
                    }
                }
            }
        }
        
        
        
    }
    
    
}
print(count)

후기

플러그에 가전제품을 꽂을때 여러가지 조건에대해 소거하는 방식으로 하였다.

여러가지 조건들을 거쳐오면서 이게 그리디방식인지는 아직까지는 잘 모르겠다.

다만 여러가지 조건들을 고려해야한다고 생각했다.

플러그에 꽂을때

1. 플러그에 꽂을 자리가 있는가?

2. 플러그에 이미 같은 전자제품이 꽂혀있는가?

3. 플러그에 있는 가전제품들 중에 무얼 빼야 가장 최소한으로 빼는 것인가?

1번과 2번은 배열 안에 조건문을 통해 소거하였고, 문제는 3번이였다

여기서 최적의 해를 구하는 그리디방식이 쓰여졌다.

3-1) 플러그에 꽂혀있는 가전제품은 앞으로 쓰이지 않는가?

3-2) 플러그에 꽂혀있는 가전제품은 앞으로 몇번째에 쓰이는가?

3-3) 플러그에 꽂혀있는 가전제품중에 가장 최근에 쓰이는 제품은 어느것이고, 가장 나중에 쓰이는제품은 어느것인가?

이러한 조건을 생각해서 플러그에서 가전제품을 뽑을땐 아예 쓰이지않는 제품이나, 가장 나중에 사용될 제품을 뽑아야 최소한으로 뽑는것이다 라고 생각을 하였다.

indexArr 배열을 plug 배열과 같이 만들어서 plug배열에 있는 가전제품의 번호가 

앞으로 사용될 useList 배열에서 몇번째 인덱스에 있는지 indexArr에 저장하였다.

사용된다면 -> index 저장 , 사용되지않는다면 -> -1 저장

indexArr의 최대값은 곧, 맨 나중에 사용될 가전제품이기에 우선적으로 뽑아서 다른 가전제품으로 교체하였다

arr enumerated()

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다