BOJ_2622 : 삼각형만들기

👉 문제링크

2622번: 삼각형만들기

---

---

🔸 문제 분석 🔸

• 주어지는 성냥의 개수 n으로 만들 수 있는 삼각형의 종류를 출력한다.
• 조건은 다음과 같다.
  • 삼각형은 가장 긴 변의 길이가 나머지 변들의 합보다 작아야 한다. (삼각형의 조건)
  • 성냥의 개수는 n개이다.
  • 중복을 제거해야 한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int answer = 0;

        for (int a = 1; a <= n-2; a++){
            for (int b = a; b <= n-2; b++){
                int c = n - (a+b);
                if (c < b) break;
                if (a+b > c) answer++;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• 세 변을 a, b, c로 나누어 생각한다.
  • c는 가장 긴 변의 길이이다. n에서 a+b를 빼서 구한다.
  • c보다 더 긴 변이 나오면 중복이다.
  • a+b가 c보다 커야 삼각형이 만들어진다.

---

🔸 end 🔸

• 간단한 문제였고 키포인트였던 삼각형의 생성 조건도 먼저 알아차렸다. 하지만 반복문을 어떻게 돌려야 할 지 몰라서 첫 풀이는 너무 비효율적으로 됐고, 시간초과가 나왔다.