🖥️ 삼각형의 완성조건 (2)

코딩테스트 연습 - 삼각형의 완성조건 (2)

문제 설명

---

선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.

• 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.

삼각형의 두 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 나머지 한 변이 될 수 있는 정수의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

---

• sides의 원소는 자연수입니다.
• sides의 길이는 2입니다.
• 1 ≤ sides의 원소 ≤ 1,000

입출력 예

---

sides result

[1, 2]	1
[3, 6]	5
[11, 7]	13

입출력 예 설명

---

입출력 예 #1

• 두 변이 1, 2 인 경우 삼각형을 완성시키려면 나머지 한 변이 2여야 합니다. 따라서 1을 return합니다.

입출력 예 #2

• 가장 긴 변이 6인 경우
  • 될 수 있는 나머지 한 변은 4, 5, 6 로 3개입니다.
• 나머지 한 변이 가장 긴 변인 경우
  • 될 수 있는 한 변은 7, 8 로 2개입니다.
• 따라서 3 + 2 = 5를 return합니다.

입출력 예 #3

• 가장 긴 변이 11인 경우
  • 될 수 있는 나머지 한 변은 5, 6, 7, 8, 9, 10, 11 로 7개입니다.
• 나머지 한 변이 가장 긴 변인 경우
  • 될 수 있는 한 변은 12, 13, 14, 15, 16, 17 로 6개입니다.
• 따라서 7 + 6 = 13을 return합니다.

제출 코드

---

2022년 12월 30일

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> sides) {
    sort(sides.begin(), sides.end());
    return sides[0] * 2 - 1;
}

sides result

[1, 2]	1
[3, 6]	5
[11, 7]	13

아무 생각 없이 예제 보다가 규칙인가 싶어서 풀었다.

그리고 찝찝해서 아이패드에 경우의 수를 써가면서 해보았다.

가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다. 이게 큰 힌트다.

구하는 임의의 수를 x라고 하고 2번 예제를 보면

1. 6이 가장 긴 변이라고 가정할 때7이 되면 6이 가장 긴 변이라는 가정이 깨진다.
2. 3 + x > 6 ⇒ x = 4, 5, 6
3. x가 가장 긴 변이라고 가정할 때6이 되면 가장 긴 변이라는 가정이 깨지고, 9가 되면 힌트 내용이 성립되지 않는다.
4. 3 + 6 > x ⇒ x = 7, 8

추가로, 가장 긴 변을 x가 아닌 sides 원소 중 큰 수라고 가정했을 때 x 역시 그 값이 될 수 있다. 하지만 x가 가장 큰 변이라고 했을 때에는 sides 원소 2개 합한 것보다 작지만 sides 원소 중 가장 큰 값보다는 커야 하기 때문에 1개가 더 줄어든 것을 볼 수 있다.