[풀이]백준 풀이(VIII/16936 등 )

문제풀이

[RE]나3곱2(16936, BFS 응용)

• 시작정수(x)를 (/3) 또는 (*2)를 반복하여 수열 A를 만든 뒤
• 숨바꼭질은 BFS로 풀 수 있는 기본 문제
• 숨바꼭질5와 비슷한 문제이다.
• 수학적지식(소인수분해)를 약간 이용한다.
• 3의 개수는 줄어들어야만하고 2의 개수는 늘어나야만 한다.

3은 나누어지기만 하므로 3의 개수가 많은 그룹이 무조건 앞에 있다.

의문1. 10^18이 longlong으로 받아지는가?

의문2. vector<pair<int, long long» a(n) 의 정확한 의미..

의문3. a[i].first를 반대로 넣는 이유

• 소팅할 때 순서때문에 그렇다.

캠프준비(16938, 구현)

• 2<=N<=15, N=문제의 개수
• L<=난이도의합<=R, 최고난이도 - 최저난이도 >= X
• 최악의 경우의 수 = 2^N = O(2^N)
• 어려운 것: 최고난이도, 최저난이도 (무엇을 선택하는지에 따라 계속 변경됨)

풀이1과 2는 조삼모사

풀이1. 구현 후 필요한 조건만을 나열해서 전체 확인

풀이2. 선택과 동시에 모든 것을 처리함(재귀형태, 인자가 많다)