[백준(BOJ)] 18429번 근손실 C++

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

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

 

18429번: 근손실

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로

www.acmicpc.net

 

 

어떤 문제인가?

ㅋㅋㅋ참 웃긴 문제이다.

간단하게 문제를 설명하자면 하루에 운동을 마쳤을 때 중량이 500 이하로 되지 않게 하는 루틴을 짜면 된다.

정확히 루틴을 짜는 것이 아니라 가능한 경우의 수를 구하면 된다.

 

 

 

접근 방법

일단 가능한지 불가능한지를 확인하긴 위해선 루틴의 순서가 필요하다.

이 경우에는 순열을 사용해야 한다.

 

경우의 수를 모두 측정하기 위해선 모든 루틴을 탐색(완전 탐색)을 해야 한다.

 

int n, k;
cin >> n >> k;
int arr[n + 1];

for (int i = 0; i < n; i++) {
    cin >> arr[i + 1];
}

간단하다. 문제에서 요구하는 변수들을 입력받고 배열에 중량 증가량을 저장한다.

 

vector<int> kit;

for (int i = 1; i <= n; i++) {
    kit.push_back(i);
}

 

kit라는 벡터에 1부터 n까지 저장한다.

따라서 벡터에는 운동 키트 번호

배열에는 중량 증가량이 저장되어있다.

 

 

int cnt = 0;

 

경우의 수를 카운트할 cnt변수를 선언해준다.

 

 

do {
    int total = 500;
    for (auto iter = kit.begin(); iter != kit.end(); iter++) {
        total += arr[*iter];
        total -= k;
        if(total < 500){
            break;
        }
    }
    if (total >= 500) {
        cnt++;
    }
} while (next_permutation(kit.begin(), kit.end()));

 

이제 next_permutation함수를 통해 순열을 구할 것이다.

실행문에 for문을 통해 순열이 된 벡터를 탐색한다.

탐색하며 500에 운동 증가량을 더하고 중량 감소량을 빼준다.

즉 for문 한 번이 하루인 것이다.

이때 중량이 500 이하가 된다면 break를 통해 탈출하고 다음 순열로 넘어간다.

당연히 경우의 수는 증가하지 않는다.

 

cout << cnt;

이렇게 모든 순열을 탐색한 다음경우의 수를 출력해주면 끝이다.

 

 

무엇이 어려웠는가?

문제를 읽고 순열을 사용해야겠다는 것을 파악하고 next_permutation함수를 알았다면 

큰 어려움 없이 풀 수 있었던 문제인 것 같다.

문제에서 요구하는 구현 자체가 어렵진 않았다.

 

 

배운 점

문제를 읽고 순열을 사용해야 함을 알았지만 이를 어떻게 구현해야 할지는 잘 몰랐다.

선배님께서 가르쳐주신 next_permutation함수를 생각해 문제를 해결할 수 있었다.

stl에 내장되어있는 다양한 함수들을 더 많이 알고 싶다는 생각을 했다.

또, next_permutaion함수를 사용하지 않고 순열을 구현해보고 싶다.

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

[백준(BOJ)] 10819번 차이를 최대로 C++  (0) 2022.08.07
[백준(BOJ)] 16457번 단풍잎 이야기 C++  (0) 2022.08.07
[백준(BOJ)] 9663번 N-Queen C++  (0) 2022.08.06
[백준(BOJ)] 3036번 링 C++  (0) 2022.08.02
[백준(BOJ)]골드바흐의 추측(에라토스테네스의 체) C++  (0) 2022.08.01
  1. 어떤 문제인가?
  2. 접근 방법
  3. 무엇이 어려웠는가?
  4. 배운 점
'백준 문제풀이(BOJ PS)' 카테고리의 다른 글
  • [백준(BOJ)] 10819번 차이를 최대로 C++
  • [백준(BOJ)] 16457번 단풍잎 이야기 C++
  • [백준(BOJ)] 9663번 N-Queen C++
  • [백준(BOJ)] 3036번 링 C++
팜준
팜준
팜준
코드가 자라나는 텃밭
팜준
전체
오늘
어제
  • 분류 전체보기
    • 회고
    • 자료구조(Data Structure)
    • 백준 문제풀이(BOJ PS)
    • 대외활동(Activity)
    • 알고리즘(Algorithm)
    • 운영체제(OS, Operating System)
    • AWS
    • 취업준비
    • 일기

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
팜준
[백준(BOJ)] 18429번 근손실 C++
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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