[백준(BOJ)] 2841번 외계인의 기타 연주 C++

2022. 7. 20. 00:27· 백준 문제풀이(BOJ PS)
목차
  1. 어떤 문제인가?
  2. 접근 방법
  3. 무엇이 어려웠는가?
  4. 배운 점

문제 : https://www.acmicpc.net/problem/2841

 

2841번: 외계인의 기타 연주

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수

www.acmicpc.net

어떤 문제인가?

기타를 치는데 가장 높은 프렛의 음이 발생하는 조건이 있다.

따라서 원하는 음을 치자고 할 때 높은 프렛을 누르고 있던 손가락을 떼야한다.

원하는 음이 기존에 누르고 있던 프렛보다 높다면 상관은 없다.

 

 

이때, 입력한 n번만큼 원하는 프렛과 줄 번호가 주어졌을 때, 손가락을 가장 적게 움직이는 횟수를 출력해야 한다.

 

접근 방법

처음에는 이 문제를 vector와 pair를 사용해 프렛과 줄 번호를 저장하려고 했다.

하지만, 이를 통해 구현하려고 하니 굉장히 답답했고 어떻게 해야 할지 감이 잘 잡히지 않았다.

문제를 다시 읽으며 고민하다가 입력한 프렛과 현재 누르고 있는 프렛 중 가장 큰 프렛부터 비교하며 손가락을 누르고 있을지, 떼야할지를 정해야 한다는 생각을 통해 자연스럽게 stack을 이용할 생각을 할 수 있었다.

 

stack<int>guitar[6];

기타는 총 6줄이므로 위와 같이 선언했다.

 

손가락의 이동 횟수를 저장할 변수를 선언해준다.

int cnt=0;

당연히 0으로 초기화한다.

 

int N, P;
cin>> N >> P;

for(int i=0; i < N; i++){
    int line, plat;
    cin >> line >> plat;

 

그다음 연주 횟수, 프렛의 수를 입력받는다.

그다음 줄 번호 프렛 번호를 입력받는다. 

그다음 입력된 각 줄마다 입력된 프렛의 번호를 추가하는 방식으로 진행했다.

 

이 문제는 발생할 수 경우의 수를 모두 처리해주어야 했다.

 

 

1. 입력된 줄에 손가락이 없을 때.

if(guitar[line-1].empty()){
    guitar[line-1].push(plat);
    cnt++;
}

 

입력된 줄에 아무런 손가락도 존재하지 않으니 줄에 추가(손가락을 올린다)해주고 횟수를 증가시킨다.

 

2. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 작을 때.

else if (guitar[line-1].top() <plat){
        cnt ++;
        guitar[line-1].push(plat);
}

이 경우에는 현재 누르고 있는 프렛 중 가장 큰 프렛보다 입력된 프렛이 높으므로 입력된 프렛의 소리가 날 것이므로

손가락을 뗄 필요 없이 줄에 추가(손가락을 올린다)해주고 횟수를 증가시키면 된다.

 

 

3. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛과 같을 때.

else  if(guitar[line-1].top() == plat ){
    continue;
}

 

이 경우에는 그냥 continue를 해주면 된다.

 

4. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 클 때.

else if(guitar[line-1].top() > plat){
    while(!guitar[line-1].empty() && guitar[line-1].top() > plat){
        guitar[line-1].pop();
        cnt ++;
    }

    if(!guitar[line-1].empty() && guitar[line-1].top() == plat ){
        continue;
    }
    else{
        guitar[line-1].push(plat);
        cnt++;
    }
}

이 경우가 가장 복잡한 경우이다.

 

먼저 while문을 통해 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 작아질 때까지 반복하며

입력된 줄에 있는 프렛을 삭제(손가락을 뗀다)한다. 

이때 반복 한 번마다 횟수를 증가시킨다. 손가락을 하나 씩 떼는 것이기 때문이다.

 

그다음, 만약 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛과 같다면 continue를 통해 별도의 작업 없이 넘어간다.

 

만약 그렇지 않다면 입력된 줄에 프렛을 추가(손가락을 올린다)하고 횟수를 증가시킨다.

 

마지막으로 모든 입력이 끝난 후 손가락이 움직인 횟수를 출력하면 끝!

cout << cnt;

 

 

무엇이 어려웠는가?

먼저 자료구조를 선택하는 것부터 쉽지 않았다.

자료구조를 선택하는 것 부터 시간이 걸려서 어렵게 느껴졌다.

 

그리고 가장 어렵게 느껴졌던 것은 예외 처리였다.

1, 2, 3번 경우를 생각해내는 것은 큰 어려움은 없었다.

 

하지만 4변 경우의 예외를 처리하는 것에서 시간을 많이 잡아 먹혔다.

 

guitar[line-1].push(plat);
cnt++;

원래는 while문이 끝나면 그냥 추가를 했다. 당연히 입력된 프렛보다 큰 프렛들을 다 삭제(손가락을 뗀다)했으니 이렇게 하는 것이 맞다고 생각했다. 하지만 출력이 계속 이상하게 되어서 계속 고민했다...

 

이럴 땐 어쩌구, 저럴 땐 저쩌고~~..~~ 이렇게 하나씩 과정을 말하던 중 "같을 때는 상관없으니까 그냥 넘어가고.."를 내 입으로 직접 말했다. 그러고 3초후에 어? 엥? 하고 내 코드를 보니 같을 때에 대한 코드가 적혀있지 않았다.

왜 내 뇌는 이 코드를 작성하지도 않고 컴퓨터 탓만 했는가.....

같을 때는 그냥 넘어가야한다고 생각해서인지 내 뇌에서도 코드를 작성하지 않고 넘어가버렸다.

해결하고 나니 참 허탈스러웠다..

 

 

배운 점

 

문제를 읽으면 바로 아! 자료구조 이걸 써야지! 가 생각나야 할 텐데 아직 많이 부족하다고 문제를 풀 때마다 느끼는 것 같다.

 

예외 처리를 확실하고 꼼꼼하게 하자. 머리로는 분명 생각했던 것인데 코드를 쓸 때 빼먹는 경우가 많다고 느껴진다.

문제를 풀기 전에 먼저 머리로만 흐름을 그리지말고, 내 머리를 믿지 말고 생각한 내용을 다 패드에 적어놓고

이걸 보면서 코드를 써내려가고, 생각난 것은 다시 패드에 적고 이런 습관을 들여야 할 것 같다.

.

.

.

.

P.S. 요 며칠 컴공 고질병(거북목, 라운드 숄더 등)으로 인해 몸 컨디션이 좋지 않아서 좀 뜸했다.

몸이 불편하니 아무것도 하기가 싫어서 정말 병원 다니면서 치료받고 푹 쉬었다.

쉬는 게 질릴 때쯤 몸도 많이 괜찮아져서 오늘 블로그를 썼다.

앞으로 더 열심히해야겠다. 화이팅!

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/2841.cpp

 

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.

백준 알고리즘 문제풀이 기록 레포짓입니다. Contribute to farmJun/Algorithm_BOJ_PS development by creating an account on GitHub.

github.com

 

'백준 문제풀이(BOJ PS)' 카테고리의 다른 글

[백준(BOJ)] 1406번 에디터 C++  (0) 2022.07.25
[백준(BOJ)] 10799번 쇠막대기 C++  (0) 2022.07.25
[백준(BOJ)] 2346번 풍선 터뜨리기 C++  (0) 2022.07.19
[백준(BOJ)] 17219번 비밀번호 찾기 C++  (0) 2022.07.12
[백준(BOJ)] 7785번 회사에 있는 사람 C++  (0) 2022.07.12
  1. 어떤 문제인가?
  2. 접근 방법
  3. 무엇이 어려웠는가?
  4. 배운 점
'백준 문제풀이(BOJ PS)' 카테고리의 다른 글
  • [백준(BOJ)] 1406번 에디터 C++
  • [백준(BOJ)] 10799번 쇠막대기 C++
  • [백준(BOJ)] 2346번 풍선 터뜨리기 C++
  • [백준(BOJ)] 17219번 비밀번호 찾기 C++
팜준
팜준
팜준
코드가 자라나는 텃밭
팜준
전체
오늘
어제
  • 분류 전체보기
    • 회고
    • 자료구조(Data Structure)
    • 백준 문제풀이(BOJ PS)
    • 대외활동(Activity)
    • 알고리즘(Algorithm)
    • 운영체제(OS, Operating System)
    • AWS
    • 취업준비
    • 일기

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 완전탐색
  • 깃허브
  • 자료구조
  • 알고리즘
  • 일기
  • DFS
  • 깃
  • 깊이우선탐색
  • 그리디알고리즘
  • java
  • DP
  • 다이나믹 프로그래밍
  • deque
  • 백트랙킹
  • 자바
  • 백준
  • 덱
  • BFS
  • 그래프탐색
  • 큐

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
팜준
[백준(BOJ)] 2841번 외계인의 기타 연주 C++
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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