블로그 이사 중입니다 >> gumgood.github.io

[BOJ] 2622 삼각형만들기 본문

Problem Solving/문제 풀이

[BOJ] 2622 삼각형만들기

gumgood 2019. 2. 14. 17:08

성냥깨비의 수가 \(n \in Z^{+}\)일 때, 세 개의 변을 각각 \(a, \ b, \ c\)라고 하자.


\(a,b,c \in Z^{+} \ such \ that \ 0 \le a \le b \le c \ \land \ a+b+c=n\)


세 변이 삼각형을 이루려면 다음을 만족해야 한다.


\(a+b\gt c\)


위의 조건들로부터 가능한 \(c\)의 범위를 구할 수 있다.


\(a \le c\)

\(\Rightarrow a + b \le 2c\)

\(\Rightarrow a + b + c \le 3c\)

\(\Rightarrow n \le 3c\)


\(a+b \gt c\)

\(\Rightarrow a+b+c \gt 2c\)

\(\Rightarrow n \gt 2c\)


\(\therefore {n \over 3} \le c \lt {n \over 2}\)


각 \(c\)에 대해 가능한 \(b\)의 범위도 구할 수 있다. \(b\)가 결정되면 \(a\)도 결정된다.


\(a \le b \le c\)

\(\Rightarrow a=n-b-c \le b \le c\)

\(\Rightarrow {n-c \over 2} \le b \le c\)


가능한 \(c\)는 \(O(n)\)가지이고 각 \(c\)에 대해 \({n-c \over 2} \le b \le c\)를 만족하는 \(b\)의 갯수는 \(O(1)\)에 구할 수 있으므로

\(O(n)\)에 구할 수 있다


<소스>


'Problem Solving > 문제 풀이' 카테고리의 다른 글

[BOJ] 2185 직사각형의 합집합  (0) 2020.01.07
[BOJ] 2622 삼각형만들기  (0) 2019.02.14
14891 톱니바퀴  (0) 2019.01.17
14503 로봇 청소기  (0) 2019.01.17
1153 네 개의 소수  (0) 2019.01.15
3163 떨어지는 개미  (0) 2018.12.26
0 Comments
댓글쓰기 폼