(프로그래머스 C++)상자 꺼내기

https://school.programmers.co.kr/learn/courses/30/lessons/389478

프로그래머스

 

복잡하게 공식을 찾아내는 것보다,

brute force로 하는게 더 빠르다고 느낀 문제.

 

문제의 핵심은 순서대로 숫자를 늘릴지, 역순으로 숫자를 늘릴지인 것 같다.

 

#include <string>
#include <vector>

using namespace std;

int getFloor(int n, int w) {
    return (n / w) + (n % w == 0 ? 0 : 1);
}

int solution(int n, int w, int num) {
    int answer = 0;
    int top_floor = getFloor(n, w);
    int index = -1;
    
    for (int i = 1; i <= top_floor; i++) {
        bool is_asc = i % 2;
        int current_num = (i * w) - (is_asc ? w - 1 : 0);
        
        for (int j = 1; j <= w; j++) {
            if (current_num <= n && (current_num == num || j == index)) {
                index = j;
                ++answer;
            }
            current_num += (is_asc ? 1 : -1);
        }
    }
    
    return answer;
}

 

 

1. init

우선 박스를 쌓았을 때의 최고층의 높이를 구해준다.

최고층의 높이(top_floor) = (n을 w로 나눴을 때의 몫) + (n을 w로 나눴을 때의 나머지가 있으면 1, 없으면 0)

index는 타겟이 되는 박스가 위치한 인덱스 값이다.

 

2. for문

2-1 outter for문

이중 for문으로 1부터 시작해서 최고층의 높이 * w 까지 탐색한다.

is_asc 변수는 현재 숫자를 +1 을 해줄지, -1을 해줄지 결정한다.

current_num은 현재 박스 번호로, 시작할 때는 i와 is_asc 값에 따라 결정된다.

 

예를 들어 w = 6이라고 가정한다면

1. is_asc가 true인 경우는 홀수 층에 해당한다.

그러므로 처음 시작하는 숫자는 1, 13, 25..가 된다.

 

2. is_asc가 false인 경우는 짝수 층에 해당한다.

그러므로 처음 시작하는 숫자는 12, 24, 36...이 된다.

 

2-2 inner for문

i = 1 ~ 최고층의 높이

j = 1 ~ w

내부 for문에서는 current_num부터 시작해서 w 만큼 +1 or -1을 하여 current_num을 업데이트 한다.

업데이트를 하기 전에 current_num <= n && (current_num == n || index == j)인 경우, ++answer을 해준다.

 

이 조건문을 풀이하면 아래와 같다.

1. current_num은 n보다 작거나 같아야 한다.

2-1. 1번을 만족하면서, 현재 순회하는 숫자가 빼려고 하는 박스의 숫자인 경우 answer += 1

2-2. 1번을 만족하면서, 빼려고 하는 박스 위에 또 다른 박스가 있는 경우 answer += 1 (index를 이용)

 

이 조건을 먼저 체크한 후에 current_num을 is_asc에 맞게 업데이트 해주면 값을 구할 수 있다.