[BOJ] 15953번 상금 헌터 풀이 (C++) - 카카오 코드 페스티벌 2018 예선

[BOJ] 15953번 상금 헌터 풀이 (C++) - 카카오 코드 페스티벌 2018 예선

---

문제링크

https://www.acmicpc.net/problem/15953

15953번: 상금 헌터

 

풀이방법

갑자기 심심해서 백준열었다가 카카오 코드 페스티벌 문제가 있길래 열어보았다가 풀게되었는데

음... 사실 이문제는 매우 기초적인문제라 걍 하드코딩하면... 아름답게 풀린다.

else if 0<a<=1 //1등 1명

else if 1<a=<3 //2등 2명

else if 3<a<=6 //3등 3명

else if 6<a<=10 //4등 4명

..

이런식으로 이렇게 if else문으로 도배하면 된다.

근데 이렇게 그냥 하드코딩식으로만 풀면 재미없으니까..(?) 좀더 아름다운 풀이 도전 ㄱㄱ

'좀 이쁘게 아름답게 깔끔하게 풀수있는 방법이 있을까? 아무리봐도 규칙이 있을거같은데 말이지 ..'

하는 관점으로 문제를 보자.

 

a 먼저 보면 1등 1명 / 2등 2명 / 3등 3명 / 4등 4명 / 5등 5명 / 6등 6명

위에 if else 문 도배하는부분을 보면 여기서 우리는 규칙을 찾을수있다

1등은 0 < a <= 1   

2등은 0 + 1 < a <= 0 + 1 + 2  

3등은 0 + 1 + 2 < a <= 0 + 1 + 2 + 3 

4등은 0 + 1 + 2 + 3 <= a <  0 + 1 + 2 + 3 + 4

... (뒤에는 귀차나서 생략)

1~n까지 자연수의 합을 구하는 공식을 우리는 중딩시절 즈음 배웠을거다. 바로 n(n+1)/2 

이걸 코드로 짜면?

if ((i*(i + 1)) / 2 < a&&a <= ((i + 1)*(i + 2)) / 2)

이런식으로 나오겠지?

 

이번엔 b를 보자

if 1<= b < 2
else if 2 <= b < 4
else if 4 <= b < 8
else if 8 <= b < 16
else if 16 <= b < 32 

b는 1등 1명 / 2등 2명/ 3등 4명 / 4등 8명 / 5등 16명

규칙을 찾았는가?

2^0<= b < 2^1

2^1 <= b < 2^2

2^2 <= b < 2^3

2^3 <= b < 2^4

2^4 <= b < 2^5

2의 n승 형태로 나온다. 그럼 지금 생각나는건 뭐 ? 바로 비트연산자!

그럼 이걸 코드로 짜면 이런 형태가 된다.

if ((1 << i) <= b && b < (1 << (i + 1)))

 

그럼 이걸 정리해서 풀면 끝~~ 풀코드는 밑에 있으니 참고하자! 

 

혹시 비트연산자에 대해 모르겠다면 해당 링크를 참고!

https://royhelen.tistory.com/30?category=395081 

[C++] 비트마스킹, 비트마스크, 비트연산자

 

소스코드

#include <iostream>

using namespace std;

int A_Reward[6] = { 5000000, 3000000,2000000,500000,300000,100000 };
int B_Reward[6] = { 5120000,2560000,1280000,640000,320000, 0 };

int main() {
	int T;
	scanf("%d", &T);
	for (register int test_case = 0; test_case < T; test_case++) {
		int a, b;
		int sum = 0;
		scanf("%d %d", &a, &b);
		for (register int i = 0; i < 6; i++) {
			if (a != 0 && (i*(i + 1)) / 2 < a&&a <= ((i + 1)*(i + 2)) / 2) {
				sum += A_Reward[i];
			}
			if (b != 0 && (1 << i) <= b && b < (1 << (i + 1))) {
				sum += B_Reward[i];
			}
		}
		printf("%d\n", sum);
	}

	return 0;
}