1094.막대기

1094 역시 굉장히 쉬운문제이다.

이 문제는 쉽지만 포스팅하는 이유는 문제를 읽으면서 드디어 효율을 동시에 생각하기 시작했다고 느꼈기 때문이다.

이 문제는 막대기를 잘라서 자기가 원하는 X의 길이의 막대기를 만들어내는 문제이다.

푸는 방법은 다양하다. 어쩌면 비슷할 수도 있다. 왜냐하면 간단한 로직으로 누구나 풀 수 있기 때문이다.

1094번: 막대기

 

 

< Code 설명 >

#include <iostream>

using namespace std;

int stick[7] = { 64, 32, 16, 8, 4, 2, 1}; // 미리 막대기를 나눠놓음

int main() {
	int x;        // 원하는 길이 변수
	int cnt = 0;  // 막대기 숫자 세기
	cin >> x;     // 원하는 길이 입력받기
    
	while (x != 0){ // 막대기가 완성될 때까지 돌리자~
		for (int i = 0; i < 7; i++){
			if (x < stick[i]) // 저장해놓은 막대기보다 원하는길이가 짧으면
				continue;     // PASS!!
			x -= stick[i];    // 위의 조건문을 pass한다면 크기를 빼주자
			cnt++;            // 막대기 수 up!
		}
	}
	cout << cnt << "\n";
	return 0;
}

나는 이 문제를 풀 때 64길이의 주어진 막대기에 주목했다.

어처피 주어진 막대기를 반씩 잘라서 사용할 것이기 때문에 막대기의 크기는 한정적이기 때문이다.

바로 { 64, 32, 16, 8, 4, 2, 1 } 이렇게 7종류의 막대기만이 우리가 다룰 수 있는 막대기이다.

때문에 배열에 미리 넣어놓으면 굳이 반으로 자르는 로직을 구현할 필요가 없다. 

 

반드시 알아야 할 TIP!!

# 비교대상이 무언가 정해진 경우 굳이 연산을 통할 필요없이 미리 만들어놓고 비교하는 것도 하나의 방법이 될 수 있다.