[백준(BOJ)/C++] 2217번: 로프 - 코딩밥상

https://www.acmicpc.net/problem/2217

2217번: 로프

 

• 접근 방법

 모든 줄에 중량이 w/k만큼 걸린다는 말은 최소로 들 수 있는 줄의 중량값이 모든 줄에 걸린다는 뜻이다. 즉 (가장 약한 줄에 걸린 중량)*(관여한 줄의 수)가 들아올릴 수 있는 물체의 중량이다.

처음에는 줄의 최솟값을 구하고 n값을 곱한것이 답이라 생각하고 너무 쉽다 룰루랄라 했지만,

문제를 잘 읽어보면 "임의로 몇개의 로프를 골라서 사용해도 된다" 라고 나와있다. 이 문장이 키포인트였다.

시간 제한이 2초나 되어서 최솟값을 이용한 이중반복문을 사용하면 되겠구나 생각했다가 최댓값을 구하는 문제이니까 정렬을 이용하여 앞 순서부터 하나씩 비교하는게 빠르겠다고 생각하고 문제 풀이를 이어갔다.

 

 

 

• 논리 흐름(알고리즘)

위의 설명과 같이 (가장 약한 줄의 중량)*(관여한 줄의 개수)의 최댓값을 구하는 것이 문제인데, 이 두 값은 서로 상관관계로 표현할 수 있다.

때문에 벡터로 저장한 줄의 값들을 정렬해주고 for문을 사용하여 상관관계를 식으로 풀어서 써주면 시간복잡도 n으로 문제를 해결할 수 있었다.