백준 2532번 : 먹이사슬 풀이

2025. 2. 19. 19:36·Baekjoon
목차
  1. 1. 문제 링크
  2. 2. 풀이 방법
  3. 3. 전체 코드 (C++)

1. 문제 링크

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

 


2. 풀이 방법

각 동물의 번호, 동물의 활동영역의 왼쪽 위치, 오른쪽 위치가 입력으로 들어온다.

이 중에서 번호는 필요하지 않으므로, 왼쪽 위치와 오른쪽 위치를 묶어서 저장해주었다.

// 헤더
using pii = pair<int, int>;

// main 함수
vector<pii> animals;

for (int i = 0; i < n; i++) {
    int idx, l, r;
    cin >> idx >> l >> r;

    animals.emplace_back(l, r);
}

 

우선 활동영역을 정렬했는데, 왼쪽 위치에 대해 내림차순이 되도록, 왼쪽 위치가 같은 경우에는 오른쪽 위치에 대해 오름차순이 되도록 정렬했다.

struct cmp{
    bool operator()(const pii &a, const pii &b) const {
        if (a.first != b.first) {
            return a.first > b.first;
        }

        return a.second < b.second;
    }
};
sort(animals.begin(), animals.end(), cmp());

 

이후 오른쪽 위치에 대해 LIS를 적용하여 풀었다.

 

그런데 먹이사슬 조건에 따르면, (3, 4) 와 (2, 4) 같은 경우에도 먹이사슬 조건을 만족하게 되므로 일반적인 LIS와는 달리 같은 값이 여러 번 등장해도 된다. 다시 말해서, 일반적인 LIS는 strictly increasing인 가장 긴 수열을 구하는 반면, 여기서는 non-decreasing 조건을 만족하는 가장 긴 수열을 구하면 된다. 따라서 LIS를 구하는 과정에서 기존의 lower_bound 대신 upper_bound 를 대신 사용했다.

 

(쉽게 설명하면 lower_bound 를 이용하여 a 이상인 자리 중 가장 작은 자리를 찾은 후 그 자리에 a를 넣으면 선택한 수열에 a가 단 한 개만 존재할 수 있지만, a 초과인 자리 중 가장 작은 자리를 찾아서 a를 넣으면 선택한 수열에 a가 여러 개 존재할 수 있게 되므로 upper_bound 를 사용하는 것)

 

또한 완전히 일치하는 활동영역이 여러 번 중복해서 들어오는 입력도 있을 수 있기 때문에, 정렬된 활동영역 목록을 순회하면서 이전 활동영역과 완전히 일치할 경우에는 건너뛰도록 했다.

vector<int> memo;

for (int i = 0; i < n; i++) {
    // 이전 활동영역과 완전히 일치하는 경우에는 skip한다.
    if (i >= 1 && animals[i - 1] == animals[i]) {
        continue;
    }

    // 선택한 수열에 같은 값이 여러 번 등장해도 되므로 lower_bound 대신 upper_bound를 사용한다.
    auto it = upper_bound(memo.begin(), memo.end(), animals[i].second);

    if (it == memo.end()) {
        memo.push_back(animals[i].second);
    }
    else {
        *it = animals[i].second;
    }
}

 


3. 전체 코드 (C++)

  • C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/02000%2B/boj_2532.cpp

 

'Baekjoon' 카테고리의 다른 글

백준 27963번 : 합금 주화 풀이  (0) 2025.02.26
백준 33516번 : skeep 문자열 풀이  (1) 2025.02.25
백준 13459번, 13460번, 15644번, 15653번 : 구슬 탈출 1~4 풀이  (1) 2025.02.18
백준 1307번 : 마방진 풀이  (0) 2025.02.13
백준 25547번 : 신기한 숫자 풀이  (0) 2025.02.13
  1. 1. 문제 링크
  2. 2. 풀이 방법
  3. 3. 전체 코드 (C++)
'Baekjoon' 카테고리의 다른 글
  • 백준 27963번 : 합금 주화 풀이
  • 백준 33516번 : skeep 문자열 풀이
  • 백준 13459번, 13460번, 15644번, 15653번 : 구슬 탈출 1~4 풀이
  • 백준 1307번 : 마방진 풀이
인피케이
인피케이
꾸준히 성장하는 개발자, 인피케이의 블로그입니다. 백준과 깃허브 등 여러 플랫폼에서 인피케이로 활동하고 있습니다.
인피케이
인피케이 블로그
인피케이
전체
오늘
어제
  • 분류 전체보기 (22)
    • Algorithm (3)
      • Math (2)
      • Sorting (1)
    • Baekjoon (7)
    • Language (3)
      • Java (1)
      • C++ (1)
      • Python (1)
    • MarkUp (1)
      • MarkDown (1)
      • HTML (0)
    • DBMS (4)
      • Database (2)
      • MySQL (2)
      • MongoDB (0)
      • Redis (0)
    • Framework & Library (1)
      • Spring (0)
      • React Native (1)
    • IDE (1)
      • VS Code (1)
    • Developer (0)
    • SSAFY (1)
    • IT (1)

블로그 메뉴

  • 홈
  • 방명록
  • 태그
  • 글쓰기

공지사항

  • 인피케이 프로필

인기 글

태그

유클리드알고리즘
삼성청년SW아카데미
수학
정수론
jdk
CS
카톡테마블로그
인피케이
적성진단
m1맥
java
HTML
데이터베이스
Database
개발자
Python
어서와_티스토리는_처음이지
백준
SQL
예쁜카톡테마
가장긴증가하는부분수열
인피케이카톡테마
BOJ
티스토리
MySQL
개발지식
알고리즘
첫번째_글
baekjoon
SSAFY

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.3
인피케이
백준 2532번 : 먹이사슬 풀이

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.