백준 16162번 [가희와 3단 고음](C++) -yes6686- 티스토리

백준 문제 풀이: 16162 [가희와 3단 고음]

---

문제 링크: https://www.acmicpc.net/problem/16162

문제 설명:

음계의 수열이 주어질 때, 첫 음계 a에서 시작하여 공차 d를 가지는 등차수열을 따라가는 음계를 최대 몇 개 선택할 수 있는지 구하는 문제입니다. 수열의 음계를 차례로 확인하며 조건에 맞는 음계를 선택합니다.

---

문제 해결 코드

// 백준 16162 - 가희와 3단 고음
#include <iostream>
using namespace std;

int main() {
    int n, a, d;
    cin >> n >> a >> d; // 음계의 개수, 시작 값 a, 공차 d

    int cnt = 0; // 선택된 음계의 개수
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // 현재 음계 값
        if (x == a) { // 현재 음계가 등차수열의 다음 값이면 선택
            cnt++;
            a += d; // 다음 등차수열 값 갱신
        }
    }

    cout << cnt << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 음계 수열을 차례로 확인하며 등차수열의 조건(x == a)을 만족하는 경우를 카운트합니다.
  • 조건을 만족하면 등차수열의 다음 값을 갱신합니다.
• 구현 세부사항:
  • 등차수열의 시작 값 a와 공차 d를 입력받아 초기화합니다.
  • 수열의 각 음계를 확인하며 조건을 만족하면 cnt를 증가시키고, 다음 값을 갱신합니다.
• 시간 복잡도 분석:
  • 음계의 개수를 n이라 할 때, 수열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!