[백준 2622] 삼각형 만들기

• 안녕하세요. BlockDMask 입니다.

• 오늘자 문제 풀어보겠습니다.

• 오늘자 문제는 음..

• 전체 탐색? 이긴한데 조건이 있는 전체 탐색 이었습니다.

0. 제목

• 백준 2622 삼각형 만들기

• BOJ 2622 삼각형 만들기

• TriangleTriangleTriangle

1. 문제 설명

• 같은 길이의 성냥개비가 여러개 주어집니다.
  이것들을 평면에 늘어놓아서 삼각형을 만들려고 합니다.
  삼각형의 한 변은 여러개의 성냥개비를 직선으로 이어서 만들 수 있지만, 
  성냥개비를 꺾거나 잘라서 변의 한 부분을 만들 수 는 없다.

• 성냥개비 개수가 주어졌을때, 
  이들 성냥개비를 사용하여 만들 수 있는 
  서로 다른 삼각형의 개수를 구하는 프로그램을 작성하면 됩니다.

• 예를들어 9개의 성냥개비로 만들 수 있는 서로 다른 삼각형은
  아래 그림과 같이 3가지 입니다.
  

<주의사항>

• a. 주어진 성냥개비를 모두 사용하여 하나의 삼각형으로 만들어야합니다.

• b. 삼각형을 하나도 만들 수 없다면 0을 출력합니다. 
  예를 들어, 주어진 성냥개비의 수가 1,2 또는 4인 경우에는 삼각형을 하나도 만들 수 없습니다.

• c. 합동인 삼각형들은 같은 삼각형으로 봅니다.
  예를들어 성냥개비 5개를 이용하여 만들 수 있는 그림 2의 삼각형들은 같은 삼각형으로 봅니다.
  

  

• 첫째 줄에 성냥개비의 개수가 주어집니다. 성냥개비의 개수는 1 이상 50,000 이하입니다.
• 만들 수 있는 삼각형의 개수를 출력하면 됩니다.

2. 풀이 과정

삼각형이 될 조건, 즉 삼각형 결정 조건을 만족하는 삼각형을 찾으면 됩니다.

- 가장 큰 변의 길이가 나머지 두 변의 길이의 합보다 작으면 삼각형이다. -

요고 하나만 알면 이 문제를 풀 수 있습니다.
하지만, 이 문제에서 전체 성냥개비의 개수가 정해져 있고, 그 성냥개비를 다 써야만 하니,

모든 변의 길이의 합 = 성냥개비의 개수.
이 조건이 하나 더 추가 됩니다.
(+ 중복도 제거해야겠죠?)

이것을 코드로 표현을 하면

a, b, c  세개의 변(선분)으로 구현을 하면 됩니다.

가장 큰 변을 생각해야하기 때문에

c를 항상 가장 큰변 (c>=b>=a) 로 생각을 합니다.

a는 1부터 n-1 까지

b는 a보다 크거나 같은 수 부터 n-1 까지

c는 n에서 a와 b를 뺸 값 (a+b+c = n 이어야 함).

그 중 중복을 제거하기 위해서 c 값이 b값보다 작으면 break;

a+b 값이 c 값보다 크면 cnt 증가.

흐름을 한번 볼까요?

n = 9 인경우

a b c

1 1 7

1 2 6

1 3 5

1 4 4

cnt++;

1 5 3

중복 되니까 break;

2 2 6

2 3 5

cnt++;

.

.

.

이런식으로 중복값을 제외하고 탐색을 진행하면 됩니다.

3. 코드

//https://www.acmicpc.net/problem/2622
//BOJ_2622_삼각형만들기
 
#include<iostream>
using namespace std;
 
int n, cnt;
 
//입력
void input(){
    cin >> n;
}
 
//변의 길이는 (c>=b>=a) 순입니다.(c가 제일 긴변)
void solution(){
    
    for(int a=1; a<n; a++){    // a가 가장 짧은변
        for(int b=a; b<n; b++){ // b>=a
            int c = n-(a+b);
            if(c < b) break;    //중복제외
            if(b+a > c) cnt++;  //삼각형 성립하는지
        }
    }
    
}
 
//출력
void output(){
    cout << cnt ;
}
 
int main(void){
    input();
    solution();
    output();
    return 0;
}
 

4. 인증

문제출처 - https://www.acmicpc.net/problem/2622

감사합니다.

도움이 되었다면 공감 한번 부탁드립니다.!