[C/C++]BOJ #1094 막대기

yujo·2020년 5월 20일
0
post-thumbnail

문제

문제 링크 : BOJ #1094 막대기


문제접근

  • 들어올 수 있는 최대 input이 64로 굉장히 작고 수의 조합도 {64, 32, 16, 8, 4, 2, 1}로 7개 밖에 되지않기 때문에 처음엔 배열에 64 ~ 1의 값을 담고 완전탐색으로 접근해서 풀었다.
  • 그런데 이 문제는 다양한 풀이가 존재할 수 있다는 사실을 알게 됐다.
    (1). 내가 풀이한 것처럼 완전탐색으로 푸는 방법
    (2). 2진수의 특성을 이용해 N을 2로 나누면서 2진수로 변환해 1을 체크하는 방법.
    (3). 역시 2진수의 특성을 이용해 비트 연산자를 활용하는 방법(@seongwpa님이 알려주심)
  • 아래에 3가지 방법으로 풀이한 코드를 모두 첨부한다.
  • 시간복잡도는 모두 O(N)이기 때문에 해당 문제에 한해서는 어느 방법이 좋다라고 말할 수는 없지만 (1)의 풀이방법으로 푼다면 64이하의 숫자에서만 활용이 가능하고
  • 2, 3의 방법을 사용한다면 64보다 훨씬 더 큰 숫자를 입력 받을 때도 올바른 결과값을 출력할 수 있기 때문에 (2), (3)의 풀이가 더 좋다고 생각한다.

코드

(1) 완전탐색

#include <stdio.h>

int main(void)
{
	int N;
	scanf("%d", &N);

	int count = 0;
	int arr[7] = {64, 32, 16, 8, 4, 2, 1};

	for (int i = 0; i < 7; i++)
	{
		if (arr[i] <= N)
		{
			N -= arr[i];
			count++;
		}
	}

	printf("%d", count);
}

(2) 2진수 특성 활용

#include<stdio.h>

int main(void)
{
	int N;
	scanf("%d", &N);

	int count = 0;
	
	while (N > 0)
	{
		if (N % 2 == 1)
			count++;
		N /= 2;
	}

	printf("%d", count);

	return 0;
}

(3) 2진수 비트 연산자 활용(code by @seongwpa)

#include<stdio.h>

int main() {
    int X, cnt = 0;
    scanf("%d", &X);
    while (X > 0)
    {
        if (X & 1)
            cnt++;
        X >>= 1;
    }
    printf("%d\n", cnt);
}

제출 결과

(1) 완전탐색

(2) 2진수 특성 활용

(3) 2진수 비트 연산자 활용(code by @seongwpa)


  • 코드나 로직에 이해가 안 되는 점은 댓글로 알려주시면 감사하겠습니다.
profile
소프트웨어로 세상을 구하자 @42seoul @IBM C:LOUDERs

0개의 댓글