백준
백준2622 - 삼각형만들기
개발하는꼬마
2019. 11. 23. 21:53
https://www.acmicpc.net/problem/2622
2622번: 삼각형만들기
같은 길이의 성냥개비가 여러 개 주어져 있다. 이것들을 평면에 늘어놓아서 삼각형을 만들려고 한다. 삼각형의 한 변은 여러 개의 성냥개비를 직선으로 이어서 만들 수 있지만, 성냥개비를 꺾거나 잘라서 변의 한 부분을 만들 수 는 없다. 성냥개비의 개수가 주어졌을 때, 이들 성냥개비를 사용하여 만들 수 있든 서로 다른 삼각형의 개수를 구하는 프로그램을 작성하시오. 예를 들어서 9개의 성냥개비로 만들 수 있는 서로 다른 삼각형은 그림 1과 같이 3가지이다. <주
www.acmicpc.net
i, j, k 세 가지 변수를 둔 뒤 i <= j <= k를 만족하면서 i + j > k인 경우를 찾아서 센다. 먼저 k가 될 수 있는 가장 큰 경우를 구한다. 1씩 줄여가며 가장 큰 경우를 구한다. 조건으로 설정한 그 외의 경우가 들어가는 경우는 무조건 제외한다.
#include <iostream>
using namespace std;
int main() {
int n; //최대 길이
int cnt = 0; //경우의 수
cin >> n;
int k = n / 2; //최대 길이가 될 수 있는 가장 큰 수를 구한다.
while (1) {
bool flag = true; //가장 긴 변의 길이가 바뀐 경우를 체크하는 변수
for (int j = k; j > 0; j--) {
int i = n - j - k;
if (i + j <= k) { //삼각형 조건의 안 맞으면
continue; //무시
}
if (i > k) { //가장 긴 변의 길이가 바뀌면
flag = false; //flag를 false로 변환
}
if (i > j) { //i가 j보다 큰 경우
break; //탈출
}
cnt++; //경우의 수 증가
}
if (!flag) { //가장 긴 변의 길이가 바뀐 경우
break; //탐색 종료
}
k--; //가장 긴 변의 길이를 바꾼다.
}
cout << cnt;
}