99클럽 코테 스터디 17일차 TIL

백준- 31926번

입력과 복사 중 하나를 선택하여 컴퓨터 입력 시간을 최소화해야 한다.

처음 daldidalgo가 만들어지는 시간은 8초이다.

• daldi : 5번 입력
• dal : 입력된 daldi의 dal 복사
• go : 2번 입력

이후 N만큼 daldidalgo가 반복되고 마지막에 daldidan 으로 마무리된다.

 

먼저 daldidan이 만들어지는 경우는 2개이고, 둘 다 2초가 소요된다. 

• daldida 복사, n 입력
• daldidalgo ... daldida 복사, n 입력

다음으로 N만큼 반복되는 daldidalgo를 살펴보자.

n = 2
(daldidalgo) (daldidalgo) (daldida)(n) 
=> 8 + 1 + 2 =  11

n = 3
(daldidalgo) (daldidalgo) (daldidalgo daldida)(n) 
=> 8 + 1 + 2 = 11

n = 4
(daldidalgo) (daldidalgo) (daldidalgo) (daldidalgo daldida)(n)
=> 8 + 1 + 1 + 2 = 12

n = 7
(daldidalgo) (daldidalgo) (daldidalgo daldidalgo) (daldidalgo daldidalgo daldidalgo daldida)(n)
=> 8 + 1 + 1 + 2 = 12

n = 8
(daldidalgo) (daldidalgo) (daldidalgo daldidalgo) (daldidalgo) (daldidalgo daldidalgo daldidalgo daldida)(n)
=> 8 + 1 + 1 + 1 + 2 = 13

1이 더해지는 횟수에 규칙이 보인다.

n = 2, n = 3 은 1이 한 번씩 더해지고,

n = 4, n = 7 은 1이 두 번,

n = 8 은 1이 세 번...

 

2^2 의 값인 4 전까지는 한 번씩 더하고, 2^3 의 값인 8 전까지는 두 번씩 더하고 있다. 

결국, 2를 기준으로 거듭제곱만큼 1을 더하고 있다.

2^1	1 * 1
2^2	1 * 2
2^3	1 * 3
2^4	1 * 4
2^5	1 * 5

그렇다면 거듭제곱의 수를 어떻게 특정할 수 있을까.

 

거듭제곱의 수를 k 라 할 때, 1씩 증가시키고

2^k > N 조건이라면 8 + (k - 1) + 2 를 계산하여 결과값을 반환한다.

만약 2^k == N 이라면 8 + k + 2 로 계산하면 된다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int count = 8;
        int k = 1;
        while (true) {
            double powerOfTwo = Math.pow(2, k);
            if (N == powerOfTwo) {
                count += k + 2;
                break;
            } else if (N < powerOfTwo) {
                count += k + 1;
                break;
            }
            k++;
        }

        System.out.println(count);
        br.close();
    }
}

---

백준 31926번 - 밤양갱

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

 

참고

https://steadycoding-turtleman.tistory.com/entry/BEAKJOON-JAVA-31926%EB%B2%88-%EB%B0%A4%EC%96%91%EA%B0%B1

https://velog.io/@engus525/%EB%B0%B1%EC%A4%80-31926%EB%B2%88-%EB%B0%A4%EC%96%91%EA%B0%B1