[백준] 1614번 영식이의 손가락 (구현_JAVA)

구현이 점점 멀어지는 것 같아서

실버부터 다시 차근 차근 도전 중!

 

확실히 구현은 다른 것들보다

생각도 많이 하고, 시간도 오래걸리는 것 같다.

 

---

문제

 

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

1614번: 영식이의 손가락

 

 

---

설계

 

알고리즘 설계[접근방법] : 구현

고장난 손가락의 사용할 수 있는 횟수가 10억이므로 평범한 반복문으로 횟수를 세면 시간초과가 발생할 것이라 생각했다.

그래서 처음과 중간, 끝 부분을 나누고 횟수를 사칙연산으로 계산했다.

 

가장 먼처 처음이다. 처음에는 사용횟수가 0보다 크다면 무조건 1번부터 5번까지 갈 수 있다. 사용횟수가 0일 때는 다친 손가락 번호 전까지만 가능하다.

 

그 다음 중간이다. 여기서부터는 조건에 따라 횟수가 달라진다.

다친 손가락이 1번 또는 5번이라면 두번 갈때 다친 손가락을 사용한다.

하지만, 다친 손가락이 2, 3, 4번이라면, 한 번의 방향으로 갈 때마다 다친 손가락을 사용해야한다.

 

예를 들어, 다친 손가락이 1번이라고 해보자!

처음에 숫자를 세고, 4번부터 1번까지 그리고 2번부터 5번까지 숫자를 세는 과정에서 다친 손가락은 한번만 사용한다. 

 

다친 손가락이 2, 3, 4번이라고 한다면, 4번에서 1번으로 가는 과정에서 다친 손가락을 사용한다.

이 표를 보면 알 수 있듯이, 다친 손가락이 1번 또는 5번일때 다른 손가락이 다쳤을 때보다 숫자를 2배 크게 셀 수 있다.

 

마지막은 다친 손가락을 사용할 수 있는 만큼 다 사용했을 때다.

다친 손가락을 사용할 수 있는 횟수가 짝수일 때와 홀수일 때가 다른데, 그 이유는 숫자를 세는 방향이 다르기 때문이다.

홀수라면 오른쪽에서 왼쪽으로 마지막 숫자를 세고, 짝수라면 왼쪽에서 오른쪽 방향이다. 이 경우까지 고려한다면, 모든 경우의 수를 고려한 것이다!

 

풀이과정

1.

다친 손가락의 번호인 n과, 사용 가능 횟수 count를 입력받는다.

 

2.

정답 변수 answer을 초기화한다. 이 때 셀 수 있는 최대값이 10억이 넘을 수 있으므로 long 타입으로 설정한다.

 

3.

만약 count가 1보다 크거나 가정하자.

처음 방향은 무조건 가능하므로 answer에 5를 더한다.

중간 방향은 고장난 손가락 번호가 2, 3, 4번이라면 (count-1)*4를 asnwer에 더해준다.

고장난 손가락이 1 또는 5번이라면 2배이므로,  (count-1)*4*2를 answer에 더해준다.

마지막은 고장난 손가락이 1번이라면, 4-3-2 이렇게 3개만 사용 가능하므로 3을 더해주고, 고장난 손가락이 5번이라면 4-3-2-1-2-3-4 이 순서로 사용 가능하므로 7을 더해준다.

그 외의 손가락이 고장났다면, count가 홀수냐 짝수냐에 따라 방향이 다르다. 짝수라면 왼쪽에서 오른쪽 방향이므로 n-2를 더해주고, 홀수라면 오른쪽에서 왼쪽 방향이므로 4-n을 더해준다.

 

4.

만약 count가 0이라면, n-1까지만 숫자를 셀 수 있다.

 

 

 

---

코드

 

 

import java.util.*;

public class Test_1614_영식이의손가락 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//다친 손가락
		int n = sc.nextInt();
		
		//다친 손가락 사용 가능 횟수
		long count = sc.nextLong();
		
		long answer = 0;
		if(1<=count) {
			answer+=5; 										//첫 번째 
			if(n!=1 && n!=5) answer+=((count-1)*4);			//중간
			else if(n==1 || n==5) answer+=((count-1)*4*2);
			
			if(n==1) answer+=3;								//마지막
			else if(n==5) answer+=7;
			else if(count%2==0) answer+=(n-2); 		
			else if(count%2!=0) answer+=(4-n);
		}
		else {
			answer+=(n-1);
		}
	
		//출력
		System.out.println(answer);
	}
}

 

 

(❁´◡`❁)

끝!