[C++] 백준 2217번 풀이 (로프)

정민경·2023년 1월 19일
0

baekjoon

목록 보기
20/57
post-thumbnail

- 문제 (2217번) : 로프

  • 여러개를 연결한 로프로 들어올릴 수 있는 물체의 최대중량 구하기.
    • 각각의 로프가 들 수 있는 무게 w 입력받음.
    • 여러개의 로프를 연결했을 때 각각의 로프에 모두 고르게 w/k 만큼의 중량이 걸리게 됨.
    • 모든 로프를 사용하지 않아도 됨.

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 로프의 개수 N 입력
  • 둘째 줄부터 N개의 로프가 버틸 수 있는 최대 중량 입력.
    ( 10,000을 넘지 않는 자연수 )

[ 출력 ]

  • 로프를 사용해 들어올릴 수 있는 최대 중량 출력

- 문제 풀이

  • 로프를 사용해 물체를 들어 올릴 때 2개 이상의 로프를 사용하게 되면

    사용한 로프들 중에서 가장 가벼운 로프 무게 x 사용한 로프의 개수

    가 들어올릴 수 있는 무게가 된다.

  • 모든 로프를 다 사용할 필요가 없으므로 최대 중량은 다음과 같이 구할 수 있다.

    1. 가장 무거운 무게를 들 수 있는 로프 하나만 사용
    2. 가장 무거운 무게와 그 다음 무거운 무게를 들 수 있는 로프 두개 사용
      ...
    3. N개의 로프 모두 사용

    이렇게 사용할 수 있고, 각각의 상황에서의 들 수 있는 무게는

    1. 가장 무거운 무게 x 1
    2. 두번째로 무거운 무게 x 2
      ...
    3. 가장 가벼운 무게 x 로프의 개수 N

    이 된다.

  • 따라서 로프들을 사용해 들 수 있는 최대 중량은 위에서 구한 값들 중 가장 큰 값이 된다.
    이 큰값은 위에서 구한 무게들을 정렬해 가장 큰 값을 출력하면 된다.


- 최종 코드

0개의 댓글