[BOJ/Silver 3] 백준 1614 영식이의 손가락(C++)

문제 링크

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

1614번: 영식이의 손가락

 

문제

영식이는 숫자를 셀 때, 왼손을 이용한다. 엄지손가락부터 시작해서 새끼손가락까지 차례대로 하나씩 센다. 그다음에 새끼손가락까지 센 다음에는 반대로 엄지손가락으로 다시 역방향으로 센다. 영식이는 자기가 원하는 숫자가 나올 때 까지 계속해서 이 방법으로 센다. 영식이는 절대 손가락을 건너뛰지 않는다. 예를 들어 숫자 10을 셀 때는, 엄지 → 검지 → 중지 → 약지 → 새끼 → 약지 → 중지 → 검지 → 엄지 → 검지 이렇게 센다.

영식이가 손가락을 하나 다쳤다. 영식이는 오른손으로는 셀 수 없기 때문에, 왼손으로 세야 한다. 다친 손가락을 이용해서 셀 수 있는 횟수가 제한되어 있다.

영식이가 셀 수 있는 최대 숫자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영식이가 다친 손가락이 주어진다. 엄지부터 차례대로 1, 2, 3, 4, 5로 번호가 매겨져 있다. 둘째 줄에는 영식이가 다친 손가락으로 몇 번 셀 수 있는지 주어진다. 이 수는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 영식이가 셀 수 있는 수의 최댓값을 출력한다. 만약 시작도 할 수 없으면 0을 출력한다.

예제 입력 1

2
3

예제 출력 1

15

1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으니 더 이상 사용할 수 없다.

예제 입력 2

1
0

예제 출력 2

0

예제 입력 3

5
0

예제 출력 3

4

예제 입력 4

2
48

예제 출력 4

193

예제 입력 5

5
973

예제 출력 5

7788

예제 입력 6

3
99999

예제 출력 6

399998

알고리즘 분류

• 많은 조건 분기

풀이

몇 번째 손가락을 몇 번까지만 사용할 수 있는지에 따라 셀 수 있는 수가 전부 다르다.

우선 1번째 손가락을 X번 사용 가능하다면 (X * 8)까지만 셀 수 있다. 그리고 5번째 손가락을 X번 사용 가능하다면 (X * 8 + 4)까지만 셀 수 있다. 1번째 손가락을 0번만 사용할 수 있다면 1 이상의 수를 셀 수 없지만, 5번째 손가락을 0번만 사용할 수 있다면 4까지는 셀 수 있기 때문이고, 이 두 손가락은 양 끝에 있기 때문에 한 번 왕복 가능하고 왕복할 때마다 셀 수 있는 수가 8만큼 증가한다.

2, 3, 4번째 손가락은 사용 가능한 횟수가 홀수냐 짝수냐에 따라 수식이 달라진다. 그 규칙을 찾는 것은 어렵지 않다.
마지막으로, 사용 가능 횟수가 10억번이다. 따라서 셀 수 있는 수는 int 자료형의 범위를 넘어가기 때문에 long long형으로 바꿔준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 11
#define LL long long
#define INF 1e9

using namespace std;
LL N, M;
LL Answer = 0;

void Input() {
	cin >> N;
	cin >> M;
}

void Settings() {
	if (N == 1) {
		Answer = M * 8;
	}
	else if (N == 2) {
		if (M % 2 == 0) {
			Answer = (M * 4) + 1;
		}
		else if (M % 2 == 1) {
			Answer = (M * 4) + 3;
		}
	}
	else if (N == 3) {
		if (M % 2 == 0) {
			Answer = (M * 4) + 2;
		}
		else if (M % 2 == 1) {
			Answer = (M * 4) + 2;
		}
	}
	else if (N == 4) {
		if (M % 2 == 0) {
			Answer = (M * 4) + 3;
		}
		else if (M % 2 == 1) {
			Answer = (M * 4) + 1;
		}
	}
	else if (N == 5) {
		Answer = (M * 8) + 4;
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}