[BOJ] 2457 - 공주님의 정원 (Python, JavaScript)

 

 

아이디어

 

날짜를 정렬한 후 이전 꽃이 지기 전에 피면서 가장 늦게 지는 꽃을 선택해 나간다.

 

 

풀이 #1 (Python)

 

기본 정렬을 이용하여 날짜를 정렬한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    flowers = sorted([tuple(map(int, input().split())) for _ in range(N)])
    m = _m = 3
    d = _d = 1
    res = 1
    for sm, sd, em, ed in flowers:
        if sm > m or (sm == m and sd > d):
            res += 1
            m, d = _m, _d
        if sm < m or (sm == m and sd <= d):
            if em > _m or (em == _m and ed > _d):
                _m, _d = em, ed
                if _m > 11:
                    break
        else:
            break
    if _m > 11:
        print(res)
    else:
        print(0)

solution()

 

 

 

풀이 #2 (Python)

 

계수 정렬을 이용하여 날짜를 정렬한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    calendar = [0]*(31*12+1)
    for _ in range(N):
        a, b, c, d = map(int, input().split())
        idx, val = (a-1)*31+b, (c-1)*31+d
        if val > calendar[idx]:
            calendar[idx] = val
    m = _m = 3
    d = _d = res = 1
    for i in range(31*12+1):
        if calendar[i]:
            sm = i//31+1
            sd = i%31
            if sm > m or (sm == m and sd > d):
                res += 1
                m, d = _m, _d
            if sm < m or (sm == m and sd <= d):
                em = calendar[i]//31+1
                ed = calendar[i]%31
                if em > _m or (em == _m and ed > _d):
                    _m, _d = em, ed
                    if _m > 11:
                        break
    if _m > 11:
        print(res)
    else:
        print(0)

solution()

 

 

 

풀이 #3 (JavaScript)

풀이 #2처럼 계수 정렬을 이용해 풀이한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const N = Number(input[0]);
    let calendar = Array(31*12+1).fill(0);
    for (let i=1; i<=N; i++) {
        const [a, b, c, d] = input[i].split(' ').map(Number);
        const idx = (a-1)*31+b;
        const val = (c-1)*31+d;
        if (val > calendar[idx]) calendar[idx] = val;
    }
    let m = _m = 3;
    let d = _d = res = 1;
    for (let i=0; i<=31*12; i++) {
        if (calendar[i] > 0) {
            const sm = parseInt(i/31)+1;
            const sd = i%31;
            if (sm > m || (sm == m && sd > d)) {
                res += 1;
                [m, d] = [_m, _d];
            }
            if (sm < m || (sm == m && sd <= d)) {
                const em = parseInt(calendar[i]/31)+1;
                const ed = calendar[i]%31;
                if (em > _m || (em == _m && ed > _d)) {
                    [_m, _d] = [em, ed];
                    if (_m > 11) break;
                }
            }
        }
    }
    if (_m > 11) console.log(res);
    else console.log(0);
}

solution();