Algorithm) BOJ) 백준 1744 - 수묶기

Algorithm) BOJ) 백준 1744 - 수묶기

문제보러가기

1. 초기접근

문제 조건 해석

두 개의 수를 묶어서 곱해서 더해나가 가장 큰 수가 되게 묶는 문제다.

문제를 보고 가장 먼저 떠올린 생각은 큰 수끼리 곱하면 큰 수가 된다는 것. 따라서 정렬해서 묶어 나가면 되겠다.

음수는? 어쩔 수 없으니다 더하자. 라고 생각 하셨다면.. 저와 같이 좀 더 힘내자구요 우리..ㅠㅠ

음수와 음수를 곱하면 양수가 된다.

여기서 끝이 아니고 몇 가지 경우를 더 생각해야 한다.

1은 곱하는 것보다 더하는 것이 더 크다.

음수가 하나 남았고 0도 남아있다면 둘을 곱해서 없애버리는게 더 크다.

이렇게 3가지를 기억하면 이 문제를 풀 수 있다.

알고리즘

1. 양수, 음수와 0 으로 나눠서 배열을 만든다.

2. 양수는 오름차순, 음수는 내림차순으로 정렬한다.

3. 양수는 1보다 큰 경우에 둘씩 묶어 곱해서 더하고 나머진 더한다.

4. 음수는 둘씩 묶어 쭉 곱해서 더한다. (-1이 남았다면 0을 곱해 없애버리는게 좋고 0과 0을 곱해봤자 0)

2. 회고

경우의 수를 생각하는 연습이 많이 부족하다. 타고났다면 좋겠지만 부족하다면 연습만이 살길.

음수와 음수를 곱하면 양수가 된다..

1은 곱하는 것보다 더하는 것이 더 크다..

음수가 하나 남았다면 0을 곱해 없애버리는 것이 더 좋다..

다음엔 이러한 경우들을 생각할 수 있는 내가 되길.

3. 코드

guard let n = readLine().map({Int($0)!}) else {fatalError()}

var meetings = [(s: Int, e: Int)]()
var endTime = -1
var count = 0

for _ in 0..<n {
    guard let meet = readLine()?.split(separator: " ").map({Int($0)!}) else {fatalError()}

    meetings.append((s: meet[0], e: meet[1]))
}

// 끝나는 시간을 기준으로 정렬
meetings.sort {
    // 끝나는 시간이 같다면 시작 시간으로 정렬
    if $0.e == $1.e {
        return $0.s < $1.s
    } else {
        return $0.e < $1.e
    }

}

// 끝나는 시간이 가장 빠른 회의부터 for문
for m in meetings {
    // 현재시간(끝난시간)이 다음 회의의 시작시간보다 작거나 같다면
    if endTime <= m.s {
        count += 1
        endTime = m.e
    }
}

print(count)