본문으로 건너뛰기

389478 - 택배 상자 꺼내기

info

풀이 키워드​

스포주의

구현 수학


풀이 코드​

info
  • 메모리: 107000 KB
  • 시간: 0 ms
class Solution {
    public int solution(int n, int w, int num) {
        int lv = (num - 1) / w; // 꺼내려는 상자가 놓인 층: 0 ~
        int lastLv = n / w - 1; // 모든 상자가 놓인 맨 위층
        int left = n % w; // 남은 상자 수
        
        // offset: 왼쪽 방향으로부터의 gap
        // 홀수층이면 역방향 고려해서 offset 계산
        int offset = (lv & 1) == 1 ? w - (num - (lv*w)) + 1 : num - (lv*w);
        
        int ans = lastLv - lv + 1;
        // 남은 상자 놓이는 층이 짝수층이면 정방향
        if ((lastLv & 1) == 1) {
            if (offset <= left) ans += 1;
        }
        // 홀수층이면 역방향
        else {
            if (offset + left > w) ans += 1;
        }
        
        return ans;
    }
}

풀이 해설​

기본 구현인데 수학적 머리가 있을수록 손가락이 덜 고생하는 유형이다.

그러나 실전에선 무작정 구현으로 부딪힐 것이기에 문제를 구조화해서 풀었다.


int lv = (num - 1) / w; // 꺼내려는 상자가 놓인 층: 0 ~
int lastLv = n / w - 1; // 모든 상자가 놓인 맨 위층
int left = n % w; // 남은 상자 수
  1. 맨 아래부터 0층이라고 하자.
  2. 맨 위에 조금 박스 남는 층을 t층이라고 하자.
    • 다시 말해, t = lastLv + 1
    • 0 ~ t-1 층까지 끄집어내야 하는 상자 개수는, 상자 놓이는 순서와 무관하게 계산 가능하다.
  3. t층의 남은 상자 중에서 꺼내야 되는 녀석이 있는지 여부를 판단하면 끝!

그리고 3번을 구하기 위해, 다음의 2가지 값이 필요하다.

  • 꺼내려는 아래쪽 상자의 x축 위치
  • t층의 상자 놓는 방향 -> 정방향? 역방향?

x축 위치는 상자 놓는 방향과 무관하게 왼쪽을 기준으로 떨어진 만큼을 의미하고, offset으로 정의한다.

상자 놓는 방향은 해당 층수의 홀/짝 여부로 판단한다.

0층이 정방향이었으니 짝수 -> 정방향 / 홀수 -> 역방향이 된다.

// offset: 왼쪽 방향으로부터의 gap
// 홀수층이면 역방향 고려해서 offset 계산
int offset = (lv & 1) == 1 ? w - (num - (lv*w)) + 1 : num - (lv*w);

int ans = lastLv - lv + 1;
// 남은 상자 놓이는 층이 짝수층이면 정방향
if ((lastLv & 1) == 1) {
    if (offset <= left) ans += 1;
}
...


tip

🤔 더 깔끔한 수학 공식을 알아보자​

잘 보면 위아래로 인접한 상자 값끼리 합칠 때, 일정 패턴이 있다.

예제그림

8번 박스 있는 라인을 볼 때,

0~1층: 5 + 8 = 13 (= 6*2+1)

1~2층: 8 + 17 = 25 (= 6*4+1)

2~3층: 17 + 20 = 37 (= 6*6+1)

즉, 이를 일반화할 시 k-1 ~ k층에서 값이 w * 2k + 1 이라는 공식이 도출된다.

따라서 k와 w는 알고 있는 값이므로, num으로부터 위층 박스 값을 구하고

이 값이 n 이하인지 검사하는 방식으로 카운팅할 수 있다.


메모​

  • 2번이 하단과 같은 형태의 TC인 것 같다.
2 1 2
정답: 1