728x90
SMALL
백준 문제 풀이: 18429번 [근손실]
문제 링크: https://www.acmicpc.net/problem/18429
문제 설명:
운동을 할 때 매일 특정 무게를 들어야 하는데, 특정 순서로 운동을 진행하면 근손실 없이 모든 운동을 완료할 수 있습니다. 각 운동 키트는 무게를 증가시키지만, 매일 사용 후 일정 무게가 감소합니다.
주어진 운동 키트의 순서를 정해 근손실 없이 모든 운동을 수행할 수 있는 경우의 수를 구하는 문제입니다.
- 운동 키트 수: \( n \)
- 하루마다 무게 감소량: \( k \)
문제 해결 코드
// 백준 18429번: 근손실
#include <iostream>
using namespace std;
int arr[9]; // 운동 키트의 무게 변화 저장
int visited[9]; // 각 키트의 사용 여부 확인
int n, k; // 운동 키트 수(n)와 하루 무게 감소(k)
int ans = 0; // 가능한 경우의 수
// 깊이 우선 탐색(DFS)을 통한 순열 생성
void dfs(int d, int x) {
if (x < 0) return; // 현재 무게가 0보다 작아지면 종료
if (d == n) { // 모든 키트를 사용한 경우
ans++;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i] == 0) { // 아직 사용하지 않은 키트 선택
visited[i] = 1; // 선택 처리
dfs(d + 1, x + arr[i]); // 다음 단계로 이동
visited[i] = 0; // 선택 해제
}
}
}
int main() {
ios::sync_with_stdio(false); // 입출력 속도 향상
cin.tie(NULL); // 입출력 비동기화 해제
cin >> n >> k; // 입력: 운동 키트 수와 하루 감소량
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 운동 키트 무게 입력
arr[i] -= k; // 하루 감소량 반영
}
dfs(0, 0); // DFS 탐색 시작
cout << ans; // 가능한 경우의 수 출력
}
코드 설명
코드의 주요 로직과 사용된 알고리즘 설명:
- 핵심 알고리즘: DFS(깊이 우선 탐색)를 사용하여 운동 키트의 순열을 생성하고, 각 순열에 대해 조건을 만족하는지 확인.
- 구현 세부사항:
arr[i] -= k
: 각 키트의 효과를 하루 감소량을 고려한 값으로 변환.visited[i]
: 특정 키트가 이미 사용되었는지 확인하여 중복 사용 방지.- DFS의 종료 조건:
x < 0
: 현재 무게가 0보다 작아지면 종료.d == n
: 모든 키트를 사용한 경우 유효한 경우의 수로 카운트.
- 시간 복잡도 분석:
- DFS를 통한 순열 생성이므로 시간 복잡도는 \( O(n!) \)입니다.
- \( n \)이 최대 8이므로, 최대 \( 8! = 40,320 \)번의 순열 탐색이 이루어질 수 있습니다.
결과
실행 결과: 입력된 운동 키트에 대해 근손실 없이 모든 운동을 수행할 수 있는 경우의 수가 정확히 출력됩니다.
다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!
728x90
LIST
'BAEKJOON > 브루트포스' 카테고리의 다른 글
백준 9196번 [정수 직사각형](C++) -yes6686- 티스토리 (0) | 2024.12.13 |
---|---|
백준 10655번 [마라톤 1](C++) -yes6686- 티스토리 (0) | 2024.11.22 |
백준 3085번 [사탕 게임](C++) -yes6686- 티스토리 (2) | 2024.11.15 |
백준 9742번 [순열](C++) -yes6686- 티스토리 (0) | 2024.11.15 |
백준 8892번 [팰린드롬](C++) -yes6686- 티스토리 (0) | 2024.11.14 |