<알고리즘 문제풀이&연습>/[C++] 백준

[백준 2622] 삼각형 만들기

사용자 BlockDMask 2017. 10. 19. 18:30
반응형
  • 안녕하세요. 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. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//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+> c) cnt++;  //삼각형 성립하는지
        }
    }
    
}
 
//출력
void output(){
    cout << cnt ;
}
 
int main(void){
    input();
    solution();
    output();
    return 0;
}
 
cs


4. 인증


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

감사합니다.

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

반응형