처음 풀이 ( link )


문제 풀이

자물쇠 숫자 3개를 tuple<int, int, int>로 처리하고, 숫자 사이의 차이를 abs 이용해서 계산한다. 다만, modulo 연산에서 -를 지원하지 않기 때문에 dial number - 2 ( modulo -2) 보다 큰 경우도 고려한다. 3중 루프를 O(N^3)이지만 최대 dial number 100 을 생각하면, 속도에 문제가 될 것 같지는 않다. 필요하다면, key number 에서 5x5x5 로 가능한 숫자 배열을 작성하고, 그 배열 숫자들로만 루프를 돌리면 좀 더 빨라질 것 같다. 중복 제거를 위해서 set 에 무조건 입력하고, 중복이 제거된 결과의 수만 조회 했는데, 입력하기 전에 조회를 하고 없으면 입력하도록 하는것도 방법이 될 수는 있을 것 같다. 효율성은 find를 하고 없으면 입력하는것이 조금은 더 좋을 것 같다.

프로그램 내용

더보기
#define MAX_DIAL 100

/// tuple<int, int, int> key vs tuple<int, int, int> dest check
bool check_distance(tuple <int, int, int> key, tuple <int, int, int> dest, int dial_num);
{
    int a, b, c;
    int x, y, z;
    tie(a,b,c) = key;
    tie(x,y,z) = dest;
    int dist1, dist2, dist3;

    dist1 = abs(a-x);    dist2 = abs(b-y);    dist3 = abs(c-z);

    if ((dist1 <= 2 || dist1 >= dial_num-2)
        && (dist2 <= 2 || dist2 >= dial_num-2)
        && (dist3 <= 2 || dist3 >= dial_num-2) )
        return true;
    else
        return false;
}

int main() {
    /// Read requirement
    int dial_num = 0;
    fin >> dial_num;

    int f1, f2, f3;
    fin>> f1 >> f2 >> f3;

    int m1, m2, m3;
    fin>> m1 >> m2 >> m3;

    set <tuple<int,int,int>> c_codes;

    tuple <int, int, int> f_key = make_tuple(f1, f2, f3);
    tuple <int, int, int> m_key = make_tuple(m1, m2, m3);

    for(int id1=0;id1 < dial_num ; ++id1)
        for (int id2 = 0; id2 < dial_num; ++id2)
            for(int id3= 0; id3 < dial_num; ++id3)
                tuple <int, int, int> c_key = make_tuple(id1, id2, id3);
                /// check distance 1d1 with f1/m1, id2 with f2/m2, id3 with f3/m3
                if(check_distance(f_key, c_key, dial_num))
                    c_codes.insert(c_key);
                if(check_distance(m_key, c_key, dial_num))
                    c_codes.insert(c_key);

    if (dial_num < 6)
        fout << dial_num * dial_num * dial_num << endl;
    else
        fout << c_codes.size() << endl;

 

 

Chapter 1. Getting started (link)

출처: https://cses.fi/problemset/task/1632


문제 설명

In a movie festival, n movies will be shown.  movie club consists of k members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

입력 

The first input line has two integers n and k: the number of movies and club members.

After this, there are n lines that describe the movies. Each line has two integers aa and bb: the starting and ending time of a movie.

출력

Print one integer: the maximum total number of movies.

입력 예

5 2
1 5
8 10
3 6
2 5
6 9

출력 예

4

제약조건

  • 1 <= k <= n <= 2x10^5
  • 1 <= a <= b <= 10^9

문제 풀이 내용

입력받은 영화 시작시간과 끝나는 시간을 이용해서, (영화시간, 시작/끝, 영화순서) 를 영화시간을 기준으로 정렬한다. 영화시작시간이면 클럽 맴버를 보내고, 끝나는 시간이면 본 영화수를 증가시키고, 영화 보고 있는 클럽 맴버수를 감소 시킨다.  

프로그램 내용

더보기
...
    vector <tuple<int, int>> m_time;

    for(int idx=0; idx < n_movie; ++idx)
        cin >> start_time >> end_time ;
        m_time.push_back({end_time, start_time});

    sort(m_time.begin(), m_time.end(), greater<tuple<int, int>>());

    vector<tuple<int, bool, int>> m_schedule(2*n_movie);

    for (int idx = 0; idx < n_movie; ++idx)
        tie(end_time, start_time) = m_time[idx];
        m_schedule[2*idx] = {start_time, 0, idx};
        m_schedule[2*idx + 1] = {end_time, 1, idx};

    sort(m_schedule.begin(), m_schedule.end());

    set <int> c_movie;
    int ct_member=0;
    int ct_movie=0;

    for (int idx=0; idx < 2*n_movie; ++idx)
        int m_time, m_idx;
        bool flag;
        tie(m_time,flag,m_idx) = m_schedule[idx];

        if(!flag) /// flag == 0, movie start time -> club member see
            c_movie.insert(m_idx);
            ct_member++;
        else if( c_movie.count(m_idx)) /// movie end,
            c_movie.erase(m_idx);
            ct_member--;
            ct_movie++;

        if ( idx < 2*n_movie -1 && get<0>(m_schedule[idx+1]) == m_time)
            continue;

        if (ct_member > n_member) /// can not exceed max member
            c_movie.erase(c_movie.begin());
            ct_member--;
...

 

Sorting and Searching link )

'CSES' 카테고리의 다른 글

CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1141


문제 설명

You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

입력

The first input line contains an integer n: the number of songs.

The next line has n integers k)1,k_2,,k_n: the id number of each song.

출력 

Print the length of the longest sequence of unique songs.

입력 예

8
1 2 1 3 2 7 4 2

출력 예

5

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= k_i <= 10^9

문제 풀이 내용

입력받은 노래 목록을 set에 저장하며 중복목록을 확인한다. 중복목록이 나오면, 중복목록이 나오기 전에 있는 목록들을 지운다. 

노래 목록이 끝나면, set의 크기를 출력한다.

프로그램 내용

더보기
...
    long num_array[nSong] = {0};

    for (int idx = 0; idx < nSong; idx++)
        cin >> num_array[idx];

    set <int> slist;

    int id=0, idx=0;
    int sCount=0;

    while (idx < nSong)
        if ( slist.count(num_array[idx]))
            sCount = max(sCount, idx-id);
            while( num_array[id] != num_array[idx])
                slist.erase(num_array[id]);
                id++;
            id++;
        else
            slist.insert(num_array[idx]);
        idx++;

        sCount = max(sCount, idx-id);
...

 

Sorting and Searching link )

'CSES' 카테고리의 다른 글

CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28
CSES 2. Towers (1073)  (0) 2019.09.28
CSES 2. Stick Lengths (1074)  (0) 2019.09.26
CSES 2. Maximum Subarray Sum (1643)  (0) 2019.09.26
CSES 2. Sum of Two Values (1640)  (0) 2019.09.26

출처: https://cses.fi/problemset/task/1621


문제 설명

You are given a list of n integers, and your task is to calculate the number of distinct values in the list.

입력 양식

The first input line has an integer n: the number of values.

The second line has n integers x_1,x_2,,x_

출력

Print one integers: the number of distinct values.

입력 예

5
2 3 2 2 3

출력 예

2

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= x_i <= 10^9

문제 풀이 내용

입력을 읽어 들여서 set에 입력하여 중복을 제거하고,  set size를 출력한다.

프로그램 내용

더보기
...
    set <long> distinct;

    for (int idx=0; idx<nInput; ++idx)
        distinct.insert(numbers);

	cout << distinct.size() << endl;

 

Sorting and Searching ( link )

'CSES' 카테고리의 다른 글

CSES 2. Ferris Wheel (1090)  (0) 2019.09.25
CSES 2. Apartments (1084)  (0) 2019.09.24
CSES 2. Sorting and Searching  (0) 2019.09.24
CSES 1. Chessboard and Queens (1624)  (0) 2019.09.23
CSES 1. Apple Division (1623)  (0) 2019.09.23

+ Recent posts