Algorithm: 택배 상자 꺼내기

calico·2025년 8월 5일

Algorithm

목록 보기

3/16

https://zzaekkii.tistory.com/m/33

1. 문제 상황

상자가 1부터 n까지 번호가 매겨져 있다.
바닥에 w개씩 '왼→오' 방향으로 놓고,
그 위에는 다시 w개를 '오→왼' 방향으로 놓고,
이렇게 위아래로 ㄹ자로 교차 쌓인 구조!
예시) n=22, w=6

층0  1  2  3  4  5  6
층1 12 11 10  9  8  7
층2 13 14 15 16 17 18
층3 24 23 22 21 20 19
...

※ 실제 번호는 순서대로 쌓이므로 값은 다를 수 있음, 이해를 위한 예시

2. 뭐가 중요한가?

"num번 상자 위에 뭐가 있지?"
즉, num과 같은 세로 column(열) 위에 있는 상자들을 세야 한다는 뜻!

→ 예를 들어, num=8이라면 8 위에는 17, 20번 등 '같은 열'의 번호가 올라감.

3. 규칙 발견의 핵심

1) 층 수 (level) 구하기

한 층은 w개이므로
num이 몇 번째 층인지 → (num-1) / w (자바에서 int끼리는 자동으로 소수점 버림)
예
- num=8, w=6 이면 (8-1)/6 = 1 → 0번, 1번층 (1층)
- 단, 사용하는 코드에선 level = num/w;
- 만약 num이 w로 나눠떨어지면 (-1) 해준 것이 핵심!
  - 예) num=12, w=6 → 12/6=2, 12%6==0이니까 레벨을 1로 -1 해줌

2) 짝수층, 홀수층 방향 다름

0번째, 2번째, 4번째 ... 층은 왼→오 (순서대로)
1번째, 3번째, 5번째 ... 층은 오→왼 (역순)

그래서 같은 column에 해당되는 인덱스가 구하는 방향에 따라 달라짐!

짝수층: 1,2,3,4,5,6 → (1,2,3,4,5,6)
홀수층: 12,11,10,9,8,7 → (7,8,9,10,11,12)

여기서 중요한 건:

같은 column(=num의 column)은
- 짝수층이면 "오른쪽에서 몇 번째?" (num-1)%w
- 홀수층이면 "왼쪽에서 몇 번째?" (거꾸로 계산)

이 구조가 바로 위층의 동일한 열 좌표를 맞춰주는 핵심!

4. 위로 올라갈 때의 규칙(간격, gap) 구하기

문제의 진정한 핵심!

아래에서 위로 올라가면서 같은 열의 상자만 골라야 한다.
한 층(짝→홀, 홀→짝) 올라갈 때 상자 번호가 어떻게 바뀌는지 살펴보자.
예시
- w=6, num=8 (1,2,3,4,5,6 / 12,11,10,9,8,7 / 13,14,15,16,17,18 ...)
- 8-위 : 8, 17, 20 ...
- 위의 번호 패턴: 8→17 (+9), 17→20 (+3)

이 간격(gap)이 규칙적임.

이 규칙을 쉽게 보려면 8이 '왼쪽에서 몇번째인가' 17이 바로 위층의 같은 위치에 있는 'column'에 해당되는가 각 층의 위치가 맞춰지면, 두 층의 상자 번호 차이는 어떤 패턴(주기성)이 있음을 관찰할 수 있다!

어떻게 gap을 구할 수 있지?

바닥(현재층)에서 내 위치: (num-1) % w
위층에서 같은 column 번호
- 짝수층이면 -> (위층 첫번째 번호) + (num-1)%w
- 홀수층이면 -> (위층 마지막 번호) - (num-1)%w
이것을 수식으로 정리하면, 위층 번호 = num + gap
짝수층/홀수층마다 gap이 달라짐(반복)!
- 여기서 gap 공식은 (num + w - 1) - ((num + w - 1) % w)
- 이 값이 이번 줄의 가장 오른쪽(또는 왼쪽) 번호!
(num + w - 1) % w == num이 이번 줄의 몇 번째 칸인지
- 이 식에서 gap은 (tmp - num) * 2 + 1

5. 반복 패턴

위로 올라갈 때 마다, 위의 공식으로 gap을 더해 주기만 하면 끝!
- 단, 층 방향(짝/홀)에 따라 gap 값을 번갈아 더해줌!

6. 그래서, 어떻게 세야 하나?

처음 층의 parity(짝/홀)를 구함
위로 올라갈 때마다
- 같은 parity면 gap을 더하고,
- 반대 parity면 (2w-gap)을 더함
- num이 n보다 커지기 전까지 반복(올라갈 수 있는 제일 위까지!)
그때 올라간 단계(반복 횟수)가 곧 num번 상자부터 위에 놓인 상자 총 개수!

▶ 예시로 따라가기 (w=6, n=22, num=8)

num의 column 위에 쌓인 상자만 gap 규칙대로 계산해 쌓은 층의 개수를 센다!

수평으로 w개씩 좌우 번갈아 쌓인 ㄹ자 배열
num의 열 위만 gap 규칙으로 최상층까지 계산
짝/홀 층 구분, 간격(gap) 구하기
반복문으로 gap씩 더하면서 n 넘어가기 전까지 카운트

💡 R자형 쌓기 배열이라고 실제 그림을 그리면서, "내 위에 항상 몇 칸 건너뛰어가면 내 위에 또 상자가 있는가?" 라는 칼럼-간 반복성에 착안한 수학적 규칙이 문제의 본질입니다!

실제 상자 번호 배치

층(높이)	1번째	2번째	3번째	4번째	5번째	6번째
3	-	-	22	21	20	19
2	13	14	15	16	17	18
1	12	11	10	9	8	7
0	1	2	3	4	5	6

0층(바닥): 1 ~ 6 (왼→오)
1층: 12 ~ 7 (오→왼)
2층: 13 ~ 18 (왼→오)
3층: 19 ~ 22 (오→왼, 4개만 있음)

아래가 바닥(0층), 위로 올라가면서 1층, 2층, ... 이렇게 쌓입니다.

짝수층: 왼→오 순서, 홀수층: 오→왼 순서로 번호가 매겨져요!

8번 상자 위치 찾기

8은 1층, 2번째 칸 (0층부터 센다)
1층은 오→왼이므로, 8은 두 번째(왼쪽에서 두 번째, 즉 아래로는 8, 위로는 17, 20...)

위에 뭐가 있나?

층	8 위에 쌓인 상자 번호
1층	8 (내가 꺼내려는 상자)
2층	17
3층	20

시각화 예시 (8번 상자의 column 표시 == ★)

층	1	2	3	4	5	6
3		★20
2		★17
1		★8
0

(빈자리는 다른 번호이지만 8 위의 "column"만 표시)

이걸 코드에서 어떻게 구했냐?

처음 8번 위치의 층(level), column, parity(짝/홀) 계산
위로 갈 때마다 그 column의 상자 번호는 규칙적인 차이(gap)만큼 커짐
parity(짝/홀)에 따라 gap 다름, 8→17(gap=9), 17→20(gap=3)

감각적으로 정리

상자를 위로 쌓았을 때 특정 column(열)만 따라 올라가면 위에 올려져 있는 내 위에 있는 상자들은 gap만큼 번호가 차이가 난다!
규칙은: 왼→오/오→왼, column index(왼쪽에서 몇 번째)만 맞는 것들을 찾아서 gap씩 더한다.

(아래가 바닥, 위로 올라감)
 
  3층       20
  2층       17
  1층        8  <- 내가 찾는 상자
  0층     (없음)
 same column!!

=> 8번을 꺼내려면 20, 17, 8 = 총 3개 상자를 순서대로 꺼내야 함!

규칙

짝수층→홀수층→짝수층... 아래에서 위로 올라갈 때마다 gap(규칙적 차이)만큼 더해진다!
같은 열(column)만 추적해서 끝까지 올라간 갯수가 정답!

풀이

1. 위의 공식으로 해결



def solution(n, w, num):

	answer = 0
    
    # 몇 계층이냐
    level = num // w
    
    # 나눠 떨어지는 값은 -1 처리해야 층이 같아짐
    if(num % w == 0):
        level -= 1
    
    #짝홀짝홀
    ori_level = level % 2
    
    tmp = (num + (w - 1)) - ((num + (w - 1)) % w)
    gap = (tmp - num) * 2 + 1
    
    while num <= n:
        if level % 2 == ori_level: 
            num += gap
        else: 
            num += (w * 2) - gap
        
        level += 1
        answer += 1

    
	return answer

2. 배열로 해결


def solution(n, w, num):
    level = n // w + 1
    boxes = []
    for row in range(level):
        row_values = [row * w + i if row * w + i <= n else 0 for i in range(1, w + 1)]
        if row % 2 == 1:
            row_values.reverse()
        boxes.append(row_values)
        
    for r in range(level):
        for c in range(w):
            if boxes[r][c] != num:
                continue
            
            # 박스 발견
            answer = 0
            for i in range(level):
                answer += 1
                r+=1
                if r >= level:
                    return answer
                if boxes[r][c] == 0:
                    return answer

calico

All views expressed here are solely my own and do not represent those of any affiliated organization.