정사각형의 방 String[] room 이 있다

각 격자에는 가로 또는 세로로 타일을 놓을수 있으며 같은 방향의 타일은 하나의 타일로 처리가 가능

타일을 놓을수 없는 곳은 # 로 표시가 되어 있다

방의 바닥을 덮는데 필요한 타일의 최소 수를 리턴

room : 110개의 요소가 있는 배열, 각 요소는 110 길이의 문자열

예시 입력

1)
".....",
".....",
".....",
".....",
"....."

2) 
".......",
".#..##.",
".#.....",
".#####.",
".##..#.",
"....###"

3)
"####",
"####",
"####",
"####"

4)
"...#..",
"##....",
"#.#...",
".#....",
"..#...",
"..#..#"

5)
".#....",
"..#...",
".....#",
"..##..",
"......",
".#..#."

예시 출력

5
7
0
9
9

생각의 변화

dp 저장의 기본컨셉은 다음과 같다

이전 타일정보에 따라 현재 (i, j) 에서 가질수 있는 최소 타일수가 바뀌게 된다

따라서 이전 타일정보를 dp 인덱스로 사용하고, dp 에는 최소 타일수를 저장한다

( 타일 하나마다 2개의 상태정보가 존재하므로, 이전 타일정보는 2^가로길이 로 표현된다 )

계산을 간소화 하기위해, dp 인덱스로 이전 타일정보를 표현할때

가로타일과 # 는 0으로 표현하고, 세로타일은 1로 표현한다

(아래에서 별도로 # 채크를 하므로, 둘을 동일하게 두어도 dp 저장결과에 영향을 주지않는다)

(i, j) 에서 가로 막대를 놓을 경우 dp 인덱스는 이렇게 되고

(k << 1) & ((1 << len) - 1)

(i, j) 에서 세로 막대를 놓을 경우 dp 인덱스는 이렇게 된다

horizontal + 1

추가적으로, 막대가 늘어나지 않는 경우는, 2가지 케이스가 존재한다.

1) 위쪽 타일 세로막대 + (i, j) 세로막대인 경우

(k >> (len - 1)) % 2 == 1

2) 왼쪽 타일 가로막대 + (i, j) 가로막대인 경우

k % 2 == 1

위쪽 타일과 왼쪽 타일이 '#' 인지도 체크가 필요하다

room[i-1][j], room[i][j-1

이제, dp[0] = 0 인 상태로 시작해서 room 을 한번 순회하고 나면 dp 에 정보가 채워진다

dp 내에서 최소값을 찾아서 리턴한다

pseudo code

layout(room)
    const int len = room[0].size()

    vector<int> dp(1 << len, 99999)

    dp[0] = 0

    for i=0  i<room.size()  i++
        for j=0  j<len  j++

            vector<int> nextdp(1 << len, 99999)

            for k=0  k<(1 << len)  k++
                if dp[k] == 99999
                    continue

                horizontal = (k << 1) & ((1 << len) - 1)
                vertical = horizontal + 1

                if (room[i][j] == '#')
                    nextdp[horizontal] = min(nextdp[horizontal], dp[k])
                else
                    if (i != 0 && (room[i - 1][j] != '#') &&
                            (k >> (len - 1)) % 2 == 1)
                        nextdp[vertical] = min(nextdp[vertical], dp[k])
                    else
                        nextdp[vertical] = min(nextdp[vertical], dp[k] + 1)

                    if (j != 0 && (room[i][j - 1] != '#') &&
                            (k % 2 == 0)
                        nextdp[horizontal] = min(nextdp[horizontal], dp[k])
                    else
                        nextdp[horizontal] = min(nextdp[horizontal], dp[k] + 1)

            dp = nextdp

    int res = 99999

    for (auto d : dp)
        res = min(res, d)

    return res

무한수열 A 가 있다

i<=0 일때 Ai = 1 i>=1 일때 Ai = A[i/p]-x + A[i/q]-y 가 된다

[x] 는 x 의 내림함수를 의미한다 (ex. [3.4] = 3, [0.6] = 0)

n p q x y 가 주어질때 A의 n 번째 요소를 리턴한다 (인덱스는 0-based)

n : 0 이상, 10^13 이하 p,q : 2 이상, 10^9 이하 x,y : 0 이상, 10^9 이하

예시 입력

50, 2, 3, 4, 1
10000000, 2, 3, 10000000, 10000000
12, 2, 3, 1, 0
0, 2, 2, 0, 0
124, 45, 67, 8, 9

예시 출력

10
2
8
1
2

생각의 변화

Ai 부터 아래로 트리가 구성되므로, 깊이우선탐색으로 Ai 값을 획득할수 있다

다만, n 이 10^13 까지 가능하므로, 그대로 재귀함수를 사용하면 문제가 될것 같다

pseudo code

dfs(i)
    if i <= 0
        return 1

    return dfs(floor(i/p) - x) + dfs(floor(i/q) - y)

calc(n, p, q, x, y)

    this->p = p
    this->q = q
    this->x = x
    this->y = y

    return dfs(n)

caveat

예시 입력에서는 10^13 이 없으므로 그대로 통과되었으나, 메모화 재귀를 사용해서 계산량을 줄여야 한다.

아무 막대를 선택해서 임의의 정수길이 2개로 자른다

최대 C 번 절단 할수 있으며, 자른 막대는 다음 막대를 절단할때 사용이 가능하다

막대 절단을 완료하였을때 내림차순 정렬 기준으로 sticks[K] 의 최대값을 리턴

C : 1 ~ 1억 sticks[] : 1~50개의 int, 각 int 는 1 ~ 1억까지 가능 K : 1 ~ C + sticks.size()

이때, 리턴값의 절대오차 or 상대오차는 1e-9 미만

예시 입력

1)
{5, 8},
1, 
1

2)
{5, 8},
1,
2

3)
{5, 8},
1,
3

4)
{1000000000, 1000000000, 1},
2,
5

5)
{76, 594, 17, 6984, 26, 57, 9, 876, 5816, 73, 969, 527, 49},
789,
459

예시 출력

8
5
4
1
34.92

생각의 변화

200 160 100 80 60 20 10 C=8

K번째 최대 -> '길이 40 이상인 막대는 몇개' 로 문제를 변경

200 160 100 80 60
5   4   2   2  1 = 14

절단횟수
4   3   1   1  0 = 9

절단가능한 횟수가 9이므로 만들수 있는 막대는 14-(9-8) = 13

따라서 K가 13이하일 경우 K최대값은 40이하 K가 14이상일 경우 K최대값은 40미만

0~10억 이분탐색

midstick < K midstick >= K

cut 횟수를 저장하거나, 내림차순 정렬을 할 필요없이 min 값을 그대로 리턴해도 된다

/ 할때 long long 을 쓰지 않으면 1/3.3억 계산이 되면서 비교연산이 정상적으로 동작하지 않을수 있다

midstick 갯수는 += (stick/mid) 로 구할수 있지만 자르기전 유효한 막대 갯수 + C 가 될수도 있다

min 과 max 어떤 값을 리턴해도 괜찮다.

pseudo code

maxKth(sticks, C, K)
    min = 0.0
    max = 1000000000.0

    mid

    midstick
    initial_valid_stick

    while max-min > 1e-9  &&  max-min/max > 1e-9
        mid = (min + max) / 2

        midstick = 0
        initial_valid_stick = 0

        for (i=0  i<sticks.size()  i++)
            stick = sticks[i]

            if ((stick / mid) > 0)
                initial_valid_stick++
                midstick += (stick / mid)

        limit = initial_valid_stick + C
        midstick = std::min(midstick, limit)

        if (midstick < K)
            max = mid
        else
            min = mid

    return min

while loop 없이 하는 법에 대해

while loop 을 돌리지 않고 100회 정도 돌리는 방식도 존재한다

class CutSticks
{
public:
    explicit CutSticks() {}

    double maxKth(vector<int> sticks, int C, int K)
    {

        double low = 0;
        double high = 1e9;

        int i, j;

        for (i = 0; i < 100; i++)
        {
            long long count = 0;

            double mid = (low + high) / 2;

            long long cut = 0;

            for (j = 0; j < sticks.size(); j++)
            {
                long long next = (long)(sticks[j] / mid);

                cut += max<double>(0.0, (next - 1));

                count += next;
            }

            count -= max<double>(0.0, cut - C);

            if (count >= K)
                low = mid;
            else
                high = mid;
        }

        return low;
    }
};

width x height 크기의 판이 있다.

각 칸에는 1개의 돌을 놓는것이 가능하고, 돌과 돌 사이의 거리는 2가 되어선 안된다.

이 판에 놓을 수 있는 돌의 최대개수를 리턴

width : 1 ~ 1000 height : 1 ~ 1000

예시 입력

1)
3, 2

2)
3, 3

3)
8, 5

예시 출력

4
5
20

생각의 변화

하나의 칸 마다 돌을 놓는 경우, 놓지않는 경우, 2가지 경우가 존재하므로 1000x1000 판인 경우 2^1,000,000 경우가 나올수 있다

탐색보다는, 수식화 하기 좋은 규칙을 찾아서 계산으로 푸는게

이리저리 돌을 놓아보며 생각

왠지 2x2 네모칸이 만들어지는 느낌

짝수행 짝수열에 놓는 최대갯수
+ 짝수행 홀수열에 놓는 최대갯수
+ 홀수행 짝수열에 놓는 최대갯수
+ 홀수행 홀수열에 놓는 최대갯수
= 문제의 답

각 최대갯수들 끼리는 독립적이므로 더할수 있음

따라서 짝수행 짝수열 칸을 따로 모아서 판을 만들면 인접 칸에 돌을 놓지 않는 최대갯수를 구하는 문제로 변경 가능

다시 돌을 놓아보며 수식으로 찾아보려고 했음

시뮬레이션 -> 직관

문득 이런 생각이 듬

짝수행 짝수열 판 칸 갯수 Reven * Ceven
Reven = (height + 1) / 2
Ceven = (width + 1) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Reven * Ceven) / 2

짝수행 홀수열 판 칸 갯수 Reven * Codd
Reven = (height + 1) / 2
Codd = (width) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Reven * Codd) / 2

같은 흐름으로

홀수행 짝수열 판 칸 갯수 Rodd * Ceven
Rodd = (height) / 2
Ceven = (width + 1) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Rodd * Ceven) / 2

홀수행 홀수열 판 칸 갯수 Rodd * Codd
Rodd = (height) / 2
Codd = (width) / 2

인접 칸에 돌을 놓지 않는 최대갯수는 (Rodd * Codd) / 2

최대갯수가 1일때는 예외처리가 필요

최대갯수가 홀수일때도 예외처리가 필요

pseudo code

maxStones(width, height)
    ret = 0

    Reven = (height + 1) / 2
    Ceven = (width + 1) / 2

    square1 = Reven * Ceven

    if (square1 == 1)
        ret += square1
    else if (square2 % 2 == 0)
        ret += (square1 / 2)
    else
        ret += (square1 / 2)
        ret += 1

    Codd = (width) / 2

    square2 = Reven * Codd

    if (sqaure2 == 1)
        ret += square2
    else if (square2 % 2 == 0)
        ret += (square2 / 2)
    else
        ret += (square2 / 2)
        ret += 1

    Rodd = (height) / 2

    square3 = Rodd * Ceven

    if (square3 == 1)
        ret += square3
    else if (square3 % 2 == 0)
        ret += (square3 / 2)
    else
        ret += (square3 / 2)
        ret += 1

    square4 = Rodd * Codd

    if (square4 == 1)
        ret += square4
    else if(square4 % 2 == 0)
        ret += (square4 / 2)
    else
        ret += (square4 / 2)
        ret += 1

    return ret

검은 정사각형에서 3x3 으로 분할되는 칸토어 먼지라는 프렉탈이 있다

흑색을 'X', 백색을 '.' 로 표현하는 string[] pattern 이 주어질때,

반복 횟수 time 의 칸토어 먼지에서 패턴 매칭 횟수를 리턴한다 (부분적으로 겹치는 매칭도 허용)

time : 1 ~ 9

예시 입력

1)
{
    ".X", 
    ".."
},
1

2)
{
    ".."
},
1

3)
{
    "."
},
2

4)
{
    "X...X"
},
2

5)
{
    "X"
},
9

예시 출력

1
2
65
4
262144

생각의 변화

time 9 까지 가능

가로 3^9 (19683) 세로 3^9 (19683), 2차원 배열 불가

식으로 나타내는 법

중복이니까 [0][0] 부터 하면 너무 범위가 커지는

프렉탈, 같은 구조가 반복된다.

패턴 매칭에 사용가능한 규칙이 필요

단위를 나누기가 쉽지 않다는 생각

가로 세로 대칭성을 이용

2차원 배열을 1차원 배열 2개로 표현 둘다 검정이면 검정

패턴등장 체크를 만약 2행이면

i, j 를 고정해두고 패턴 내에서 이동하면서 체크

X 일때는 r[i] == X && c[j] == X . 일떄는 r[i] == . || c[j] == .

pseudo code

checkPattern(const string &row, const string &column, vector<string> pattern, int r, int c, int width, int height)
    for (i=0  i<height  i++)
        for (j=0  j<width  j++)
            if (pattern[i][j] == 'X')
                if (row[r+i] == 'X'  &&  column[c+j] == 'X')
                    // matched
                else
                    return false

            else if (pattern[i][j] == '.')
                if (row[r+i] == '.'  ||  column[c+j] == '.')
                    // matched
                else
                    return false

    return true

occurrencesNumber(pattern, time)
    string column = ""
    string row = ""

    string box = "X"
    string space = "."

    for (i=0; i<time; i++)
        box = box + space + box
        space = space + space + space

    column += box
    column += space
    column += box

    row = column

    width = pattern[0].size()
    height = pattern.size()

    n = pow(3, time)

    matched = 0

    for (i=0  i<=n-height  i++)
        for (j=0  j<=n-width  j++)
            if (checkPattern(row, column, pattern, i, j, width, height))
                matched++

    return matched

마지막 예제 시간초과

마지막 예제에서는 19683 x 19683 번 검사하면서, 2초를 넘긴다

생각의 변화

2차원 pattern 을 1차원 row[], col[] 로 변경한다. 행 row[i] 에 X 가 있는지, 열 col[j] 에 X 가 있는지 담아둔다

2차원 프렉탈을 1차원 패턴 C 로 변경한다. 가로와 세로가 동일한 모양이기 때문에 가능

열 마다 탐색해서, 열 끝까지 탐색이 되면 q++ 행 마다 탐색해서, 행 끝까지 탐색이 되면 p++

탐색이 끝나는 조건은

(C[i+k] == X) != row[k]
(C[j+k] == X) != col[k]

pattern 에 X 가 있다면 발견된 p 와 q 를 곱하면 매칭 갯수가 된다

하지만 X 가 없다면 매칭된 곳마다, 프랙탈 길이와 패턴 길이에 의한 식이 곱해져야 한다

패턴 세로를 M, 가로를 N, C 길이를 L 이라고 할때

p*(L-N+1) + q*(L-M+1)

p*(L-N+1)
탐색된 행의 갯수 * 한 행에서 가능한 경우

q*(L-M+1)
탐색된 열의 갯수 * 한 열에서 가능한 경우

이때 생각해봐야 하는게 있다, 가로마다 세로마다 체크했으니, 분명 중첩되는 곳이 있을것이다

중첩되는곳은 행 하나에서 q 번 매칭됬을것이다. 행은 p 번 매칭되었으므로

중복된 곳은 p*q 가 된다.

pseudo code

string getString(int time)
    if (time == 0)
        return "X"

    string s = getString(time-1)

    return s + string(s.size(), '.') + s

occurrencesNumber(pattern, time)
    M = pattern.size()
    N = pattern[0].size()

    vector<bool> row(M, false)
    vector<bool> col(N, false)

    bool flag = false

    for (r=0  r<M  r++)
        for (c=0  c<N  c++)
            if (pattern[r][c] == 'X')
                row[r] = col[c] = flag = true

    string s = getString(time)

    L = s.size()
    p = 0, q = 0

    for (r=0  r+M<=L  r++)
        int k

        for (k=0  k<M  k++)
            if ((s[r+k] == 'X') != row[k])
                break

        if (k == M)
            p++

    for (c=0  c+N<=L  c++)
        int k

        for (k=0  k<N  k++)
            if ((s[c+k] == 'X') != col[k])
                break

        if (k == N)
            q++

    if (flag)
        return p*q
    else
        return p*(L-N+1) + q*(L-M+1) - p*q

A장의 0과 B장의 1이 주어지는 게임이 있다

목표는 모든 것을 1로 바꾸는 것이다

턴 마다 정확히 K 장의 카드를 선택하고, 숫자를 반전합니다

( 현재 값 상관없이 반전 가능, 바꾼 카드를 다시 반전하는것도 가능 )

게임에서 이기기 위한 최소 턴수를 리턴하고, 불가능하면 -1 을 리턴한다

A : 0 ~ 100,000 B : 0 ~ 100,000 K : 0 ~ 100,000

예시 입력

3, 0, 3
4, 0, 3
4, 1, 3
3, 2, 5
100000, 100000, 578
0, 0, 1
4, 44, 50

예시 출력

1
4
2
-1
174
0
-1

생각의 변화

A4 B0 K3

1000 또는 0001 폼을 만든다 0001 도 가능

1111 이 되려면 0001 인 형태를 만든다

뒤집을 카드를 선택했을때 0 : A가 줄어들때 B가 늘어난다 1 : B가 줄어들때 A가 늘어난다

a -= i b += i

b -= K-i a += K-i

dfs 는 탐색제한 조건이 애매

1111 부터 탐색하고 0000 을 찾으러 간다 bfs 를 사용

직전 선택을 기억해두고, 이번 선택이 직전 선택을 원복 시키는 경우는 제외

데이터 구조가 필요할까 현재 a, 현재 b, 직전 선택, 턴 을 기억하며 탐색

pseudo code

struct data
{
    int currentA;
    int currentB;
    int prev_moveA;
    int prev_moveB;

    int turn;
};

minimalMoves(A, B, K)
    if (A == 0)
        return 0

    if (A == K  &&  B == 0)
        return 1

    if (A+B <= K)
        return -1


    queue<struct data> q

    turn = 0
    q.push({0, A+B, K, -K, turn})    // all 1

    while (!q.empty())
        struct data d = q.front()
        q.pop()

        a = d.currentA
        b = d.currentB
        prev_move_a = d.prev_moveA
        prev_move_b = d.prev_moveB
        turn = d.turn

        if (a == A  &&  b == B)
            return turn

        for (i = 0; i < K; i++)
            move_a = 0
            move_b = 0

            if (i <= a  &&  K-i <= b)
                move_a -= i
                move_b += i
                move_b -= K-i
                move_a += K-i

                if (move_a == prev_move_b  &&  move_b == prev_move_a)

                else
                    q.push({a + move_a, b + move_b, move_a, move_b, turn + 1})

    return turn

100000, 100000, 578 시간초과

100000 을 서서히 줄여가는데, 탐색범위가 지나치게 넓어지는 문제가 있다

생각의 변화

탐색 범위를 좁히기 위해 다음 생각모델을 사용한다.

1) 0의 갯수를 알면 1의 갯수를 알수 있다 -> 0의 갯수만 저장

2) bfs 시 최초로 발견된 결과가 '최소이동횟수' 이다

따라서 dist[i] 에 0 의 갯수가 i 인 때에 이동횟수를 적으면 자연스럽게

bfs 탐색을 하면서 이동횟수가 증가된다

그리고 0을 뒤집는 갯수 x, 탐색중일때의 0을 u 라고 할때

naive 하게 접근하면 0 <= x <= K 로 생각할수 있지만

실제로는 범위 제한이 있다

max_x x 는 K 보다 작아야 하고 x 는 u 보다 작아야 한다

그리고 1을 뒤집는 갯수 K-x 를 생각하면

min_x K-x 는 A+B-u 보다 작아야 한다

따라서 식으로 나타내면

max_x = min(K, u)

min_x = max(0, K-(A+B-u))

x 는 조건을 모두 만족해야 하므로 max_x 를 정할땐 min 숫자를 사용했고 min_x 를 정할땐 max 를 사용하였다

이 범위 내에서 다음 x 값인 v 를 구해본다

v 는 u 에서 시작한다 0 을 x개 뒤집으면 -x 1 을 K-x개 뒤집으면 (K-x)

따라서 식으로 나타내면

v = u + K - 2*x

pseudo code

minimalmoves(A, B, K)
    if (A == 0)
        return 0

    vector<int> dist[A+B+1, -1]
    queue<int> q

    dist[A] = 0
    q.push(A)

    while (!q.empty())
        u = q.front()
        q.pop()

        if (u == 0)
            return dist[0]

        max_x = min(K, u)
        min_x = max(0, K-(A+B-u))

        for (x=min_x  x<=max_x  x++)
            v = u + K - 2*x

            if (v >= 0 && v <= A+B && dist[v] == -1)
                dist[v] = dist[u] + 1
                q.push(v)

    return -1            

1개의 도시에서 시작해 n-1 개의 도로를 지나 모든 도시를 방문하려 한다

도시는 1번만 방문한다

roads[i] 의 j번째 문자가 Y 이면 도시 i 와 도시 j 를 연결하는 도로를 반드시 지나야 한다

존이 선택할수 있는 경로의 수를 1,000,000,007 로 나눈 나머지를 리턴

예시 입력

1)
"NYN",
"YNN",
"NNN"

2)
"NYYY",
"YNNN",
"YNNN",
"YNNN"

3)
"NYY",
"YNY",
"YYN"

4)
"NNNNNY",
"NNNNYN",
"NNNNYN",
"NNNNNN",
"NYYNNN",
"YNNNNN"

//// 2개 cycle 체크용

5)
"NYYNNN",
"YNYNNN",
"YYNNNN",
"NNNNYY",
"NNNYNY",
"NNNYYN"

예시 출력

4
0
0
24
0

생각의 변화

한 붓 지나는 건 ok, 돌아오면 중복

다 탐색하는건 x

Y 배치후 다른 경로 조합 수 음..

어디서 출발

돌아오면 안되고, 도시는 1번만 지나야 하기 때문에 Y 그룹은 항상 직선이 된다. 따라서 2가지 경우만 갖게 된다 ( Y 그룹의 원소가 2 이상인 경우 )

Y 그룹의 원소가 1 이면 1, 곱셈이므로 무시

Y 그룹을 만들려면 중복검사를 하기 편리한 너비탐색을 수행

Y 그룹들을 확보하면 이후 계산은 다음과 같다

Y 그룹들을 배치하는 경우의 수 n!
2 이상 Y 그룹들의 갯수 m

n! x m

돌아오는 경로가 있으면 예외처리 필요

너비탐색 수행 전에, 각 원소마다 dfs 로 cycle 검색 발견되면 0 리턴

사이클은 아니지만, Y가 3개 있는 경우에 대해서도 처리가 필요하다

pseudo code

factorial(n)
    if n <= 1
        return 1
    return n * factorial(n-1)

dfs(int hop, int current, int finish, vector<string> roads, vector<bool> visited)
    if hop != 0  &&  current == finish
        if hop == 2    // edge
            return 0
        else           // cycle
            return 1

    ret = 0
    i = 0

    for (auto ch : roads[current])
        if ch == 'Y'  &&  visited[i] == false
            visited[i] = true
            ret += dfs(hop+1, i, finish, roads, visited)

        i++

    return ret

countPaths(roads)
    vector<vector<int>> groups

    n = roads.size()

    vector<bool> visited(n, false)

    for (i=0  i<n  i++)
        result = dfs(0, i, i, roads, visited)

        if (result > 0)
            return 0

    for (auto &road : roads)
        y_count = 0
        for (auto c : road)
            if (c == 'Y')
                y_count++

            if (y_count == 3)
                return 0

    visited.assign(n, false)

    for (i=0  i<n  i++)
        vector<int> currentgroup
        queue<int> q

        if (!visited[i])

            q.push(i)
            visited[i] = true
            currentgroup.push_back(i)

            while (!q.empty())
                e = q.front()
                q.pop()

                j = 0
                for (auto c : roads[e])
                    if (c == 'Y'  &&  visited[j] == false)
                        q.push(j)
                        currentgroup.push_back(j)
                        visited[j] = true

                    j++

            groups.push_back(currentgroup)

    multiplier = 0

    for (i=0  i<groups.size()  i++)
        if (groups[i].size() >= 2)
            multiplier += 2

    return (factorial(groups.size()) * multiplier) % 1000000007

x1, y1 에서 x2, y2 로 이동하려 한다.

지역들은 모두 원으로 표현되어 있으며 지역의 경계가 겹치거나 접하는 일은 없다

지역 i 의 중심은 X[i], Y[i], 반경은 R[i] 로 표현된다

출발점과 도착점은 지역의 경계에 있지 않다

이동할때 지나는 최소 경계수를 리턴

예시 입력

{0},
{0},
{2},
-5, 1,
5, 1

{0, -6, 6},
{0, 1, 2},
{2, 2, 2},
-5, 1,
5, 1

{1, -3, 2, 5, -4, 12, 12},
{1, -1, 2, 5, 5, 1, 1},
{8, 1, 2, 1, 1, 1, 2},
-5, 1,
12, 1

{-3, 2, 2, 0, -4, 12, 12, 12},
{-1, 2, 3, 1, 5, 1, 1, 1},
{1, 3, 1, 7, 1, 1, 2, 3},
2, 3,
13, 2

{-107, -38, 140, 148, -198, 172, -179, 148, 176, 153, -56, -187},
{175, -115, 23, -2, -49, -151, -52, 42, 0, 68, 109, -174},
{135, 42, 70, 39, 89, 39, 43, 150, 10, 120, 16, 8},
102, 16,
19, -108

예시 출력

0
2
3
5
3

생각의 변화

그래프 화 무엇을 간선으로 하고, 무슨 일을 할까

가야하는가, 조건

현재 점이 원 안에 있는지 체크하는 식은

그래프 표현 구조는 표현해야 할까

같은 원 안에 있으면 무시 다른 원 안에 있으면

원을 순회하며 체크 둘 다 밖에거나 둘 다 안이면 무시 그 외엔 +1

pseudo code

double getDistance(int x1, int y1, int x, int y)
    // return sqrt(pow(x1 -x, 2) + pow(y1 - y, 2))
    return hypot(x1 -x, y1 -y)

leastBorders(X, Y, R, x1, y1, x2, y2)
    ret = 0
    n = X.size()

    for i=0  i<n  i++
        dist1 = getDistance(x1, y1, X[i], Y[i])
        dist2 = getDistance(x2, y2, X[i], Y[i])

        if dist1 < R[i]  &&  dist2 < R[i]

        else if dist1 > R[i]  &&  dist2 > R[i]

        else
            ret++

    return ret    

그래프 구조에 대해

트리처럼 보이는 그래프를 그리고, 탐색을 할수는 있다

매월 이자가 잔액에 추가됩니다

이자가 추가된 후 지불액이 차감됩니다

연 이율의 1/12 가 월 이율이 됩니다

대출의 price, monthlyPayment, loanTerm 이 주어질 때

대출의 연 이율을 리턴합니다.

예시 입력

1)
6800, 100, 68

2)
2000, 510, 4

3)
15000, 364, 48

예시 출력

1)
4.76837e-05

2)
9.56262

3)
7.68788

생각의 변화

계산해보면 이렇게 된다

2번 예시
연 이율 9.56%
월 이율 9.56 / 12 = 0.79%

납부    이자+   지불-    잔액
                       2000
 1     15.94   510     1505.94
 2     12.00   510     1007.94
 3     8.03    510     505.97
 4     4.03    510     0

지불 금액에서 이자의 비율은 점점 줄어들 것이다 (잔액이 줄어들고 있으니까)

연리 100% 에서 시작

잔고가 + 면 월리 -= 월리 half

잔고가 - 면 월리 += 월리 half

이분 탐색을 할때 매끄럽게 balance 가 0이 되진 않을것 같은데

abs(balance) 로 1e-n 체크

이분탐색 시에는 low mid high 를 꼭 사용해야 한다 단순히 절반한 값을 + 하거나 - 하는 경우는 이전 탐색 결과를 무시할수 있다

high-low 로 1e-9 체크

예시

0.6 정답

1 : 크다       1 - 1/2 : 0.5
0.5 : 작다     0.5 + 0.5/2 : 0.75
0.75 : 크다    0.75 - 0.75/2 : 0.375
0.375.. 

0.5 보다 더 작은 곳으로 이동하였다

pseudo code

interestRate(price, monthlyPayment, loanTerm)
    low = 0, mid = 0, high = 1

    annual_rate

    while high-low > 1e-9
        mid = (low + high) / 2

        annual_rate = mid
        monthly_rate = annual_rate / 12

        balance = price

        for (i=0  i<loanTerm  i++)
            balance += balance * monthly_rate
            balance -= monthlyPayment

        if (balance > 0)
            high = mid
        else
            low = mid

    return annual_rate * 100 

절대오차와 상대오차에 대해

high-low > 1e-9 는 절대오차이고 (high-low)/high > 1e-9 는 상대오차이다

현 문제에서는 절대오차만 봐도 괜찮다. 값이 0에 가까운, 작은 값이기 때문이다

하지만, double 의 유효숫자는 제한적이여서, 너무 큰수를 사용할 경우

low 1경, high 1경+2 일때

mid = (1경 + 1경+2) / 2 = 1경+1 이여야 하지만, 
해상도 문제로 1경 또는 1경+2 가 되어버린다

따라서 둘의 차이는 좁혀지지 않고, 무한루프에 빠질 위험이 있다

그래서 등장한 것이 상대오차이다

relative error = |a-b| / max(|a|, |b|)

n개의 작업 (1~50) 에 대해 int duration[] 과 string user[] 가 주어진다

작업 i 의 소요시간은 duration[i], 요청한 유저는 user[i] 가 된다

컴퓨터는 한 번에 1개의 작업만 처리할 수 있고 모든 사용자의 평균 대기 시간은 최소화 되어야 한다

0부터 시작하는 n개의 작업번호를, '처리순서' 대로 배열해서 int[] 로 리턴 (동률일 경우 유저 사전순서)

예시 입력

1)
{400, 100, 100, 100},
{"Danny Messer", "Stella Bonasera", "Stella Bonasera", "Mac Taylor"}

2)
{200, 200, 200},
{"Gil", "Sarah", "Warrick"}

3)
{100, 200, 50},
{"Horatio Caine", "horatio caine", "YEAAAAAAH"}

예시 출력

3 1 2 0 
0 1 2
2 0 1

생각의 변화

금방 끝나는 일부터 하면 오래 걸리는 일부터 하면

금방 끝나는 일부터 하되, 작업시간이 같은 사람이 여럿이라면

먼저 시작한 일은 다른 애들에게도 더해지므로 가급적 작은 것부터 수행

전체 합이 작은 걸로 정렬, 같은 경우 사전 순으로 정렬

일단 시작했으면 빨리 끝내는 것이 평균 낮추는 데 유리

같은 사람이면 모으는 걸로, 기존에 있는지 매번 체크

job 번호를 기억하고 있어야 한다 전체 기간도

pseudo code

struct job
{
    int totalduration;
    string user;
    vector<int> jobnumber;
};

schedule(duration, user)
    vector<job> queue

    queue.push_back({duration[0], user[0], {0}})

    n = duration.size()

    for (i=1  i<n  i++)
        found = false

        for (auto &e : queue)
            if (e.user == user[i])
                e.totalduration += duration[i]
                e.jobnumber.push_back(i)
                found = true

                break

        if (found == false)
            queue.push_back({duration[i], user[i], {i}});

    sort(queue.begin(), queue.end(), [](const job& a, const job& b) {
        if (a.totalduration == b.totalduration)
            return a.user < b.user

        return a.totalduration < b.totalduration
    })

    vector<int> res

    for (auto &e : queue)
        for (auto n : e.jobnumber)
            res.push_back(n)


    return res

초기 투자금, 매월 투자금, 주식 히스토리가 주어지고

매월 초에 주식을 구매하고, 중간에 주식을 팔지 않는다고 한다

이때, 다음 달에 더 좋은 수익률이 있으면 주식을 구매하지 않아도 된다

기간의 끝에 얻을 수 있는 최대 이익을 리턴한다

예시 입력

1)
1000, 
0, 
{
    "10 20 30", 
    "15 24 32"
}

2)
1000,
0,
{
    "10", 
    "9"
}

3)
100,
20,
{
    "40 50 60",
    "37 48 55",
    "100 48 50",
    "105 48 47",
    "110 50 52",
    "110 50 52",
    "110 51 54",
    "109 49 53"
}

예시 출력

500
0
239

생각의 변화

100 투자시 10짜리가 15로 되면 가치는 1000에서 1500으로, 차익은 1500-1000 = 500

식으로 표현하면

100 투자시 40짜리가 109 가 되면 이익은

100x(109/40) - 100

20 투자시 구매하지 않은 경우 이익은

20x1 - 20

다음에 더 좋은 투자기회가 있으면 이번에 투자하지 않아도 된다

매 회차 최적 비율 획득

금액은 무시 no tracking 리스트대로 수행 현재 금액 전체 투자

pseudo code

maximumEarning(initialInvestment, monthlyContribution, stockPrices)
    vector<int> finalPrice

    stringstream ss(stockPrices.back())

    int price
    while (ss >> price)
        finalPrice.push_back(price)

    int n = stockPrices.size() - 1

    vector<double> maxrates(n, 0)

    int k = 1

    for (auto s = stockPrices.rbegin() + 1; s != stockPrices.rend(); s++)
        double maxrate = 1

        stringstream ss(*s)

        int price
        int i = 0

        while (ss >> price)
            double r = (double)finalPrice[i] / price
            maxrate = max(maxrate, r)
            i++

        maxrate[n-k] = maxrate
        k++

    int fund = initialInvestment
    double profit = 0

    for (int i = 0; i < n; i++)
        if (i+1 < n  &&  maxrates[i] < maxrates[i+1])

        else if (maxrates[i] >= 1)
            profit += (double)fund * maxrates[i] - fund
            fund = 0

        fund += monthlyContribution

    return profit

numRed 개의 붉은 상자, 붉은 공이 있고 numBlue 개의 푸른 상자, 푸른 공이 있습니다

각 상자에는 1개의 공만 넣을수 있습니다

붉은 상자에 붉은 공이 있으면 onlyRed 점수 푸른 상자에 푸른 공이 있으면 onlyBlue 점수

나머지 경우는 bothColors 점수를 얻습니다

모든 점수를 더한 합계가 최종 점수가 될때 얻을 수 있는 최고 점수를 리턴

예시 입력

numRed, numBlue, onlyRed, onlyBlue, bothColors
2,      3,       100,     400,      200
2,      3,       100,     400,      300
5,      5,       464,     464,      464
1,      4,       20,      -30,      -10
9,      1,       -1,      -10,      4

예시 출력

1400
1600
4640
-100
0

생각의 변화

탐색범위를 줄이려면

red 는 red 에 있고 blue 는 blue 에 있는걸로 시작

서로 교환 후 값이 커졌는지 작아졌는지 체크

값이 커졌다면 계속 수행 값이 작아졌다면 원래대로

값을 별도로 체크할 필요는 없다

red 를 줄이면서

red-- blue-- mix+=2

둘다 양수거나 0일때만 수행

pseudo code

getMaximum(numRed, numBlue, onlyRed, onlyBlue, bothColors)
    r = numRed
    b = numBlue

    ret = std::numeric_limits<int>::min()

    for i=0  i<=numRed  i++

        if r-i >= 0 && b-i >= 0
            next = (r-i) * onlyRed + (b-i) * onlyBlue + (2*i) * bothColors

            ret = max(ret, next)

    return ret

둥근 테이블에 앉아 회의하는 n명의 직장인이 있다

회의 시작시 반드시 다른 사람과 악수를 해야 한다

악수는 동시에 수행하며, 악수하는 팔끼리 교차되지 않아야 한다

n명의 직장인이 하는 악수가 성립하는 조합의 수를 리턴한다

• n 은 2 ~ 50의 짝수이다

예시 입력

2
4
8

예시 출력

1
2
14

생각의 변화

가로지르는 경우에 대해 표현해보면

번호를 붙인다

짝수별로 돌면서 선택, 이때 홀수만 선택가능

이전단계가 선택한 홀수, 이번단계 홀수
O(n-1)               O(n)

0                    2 가
선택할수 있는 홀수는

1 나(2)보다 작은수     3 5 7 다 가능
3 나(2)보다 큰 수      1 넘지않게
5                     1 3 
7                     1 3 5

코드로 옮기면

if Odd(n-1) < Even(n)
    Odd(n) = all
else
    Odd(n) = Odd(n-1) 보다 작은 것들

각 선택에 따른 odd 변경은 아래로 전파되어야 한다 ret = 1

내 위치도 전파

odd 는 점점 감소, odd 가 0이 될때까지

이전 선택에 따라 odd 가 결정되니 그럼 최초 선택은

선택한건 odd 에서 제거

순회중에 변경하면 x

e+2 가 n 넘는 경우는 0 리턴 odd 가 빈 경우 1 리턴

빌때가지 순회하면서 리턴값 누적 최종적으로 획득

pseudo code

countPerfect(n)
    vector<int> odd

    for i=1  i<n  i=i+2
        odd.push_back(i)

    ret = 0
    vector<int> next_odd = odd

    for auto o : odd
        next_odd.erase(next_odd.begin())

        ret += dfs(0, o, next_odd, n)

        next_odd.push_back(o)

    return ret

dfs(e, o, odd, n)
    if e >= n
        return 0

    if odd.size() == 0
        return 1


    vector<int> next_odd
    ret = 0

    if (o < e+2)
        next_odd = odd

        for (auto _o : odd)
            next_odd.erase(next_odd.begin())

            ret += dfs(e+2, _o, next_odd, n)

            next_odd.push_back(_o)

    else
        vector<int> tmp

        for (auto _o : odd)
            if _o < o
                tmp.push_back(_o)

        next_odd = tmp

        for (auto _o : tmp)
            next_odd.erase(next_odd.begin())

            ret += dfs(e+2, _o, next_odd, n)

            next_odd.push_back(_o)

    return ret

킹 나이트는 킹 + 나이트 만큼 움직일수 있는 말이다

체스판의 크기 size 와 킹 나이트의 시작위치 start 와 최종위치 end 가 주어진다

정확히 numMoves 회만에 도착하는 방법이 얼마나 있는지 리턴한다

• 경로가 다르다면 다른 방법
• 같은 칸을 반복해서 이동하는 것도 ok (start 나 end 도 중복해서 이동가능)

예시 입력

3, {0,0}, {1,0}, 1
3, {0,0}, {1,2}, 1
3, {0,0}, {2,2}, 1
3, {0,0}, {0,0}, 2
100, {0,0}, {0,99}, 50

예시 출력

1
1
0
5
243097320072600

생각의 변화

E로 가는 경로

거꾸로 E로 가기위해 numMoves-1 에 있어야 하는 위치

S에 도달하려면

공식이 있는지 체크해보았는데, 머리만 아프고 유의미한 법칙은 나오지 않았다

Map 을 만드는 게 나을까?.. 이동기억이 필요하다

No. 기억해야 하는건 현재 얼마나 움직였는지와 현재 좌표뿐

pseudo code

howMany(size, start, end, numMoves)
    dfs(0, end[0], end[1], size, start, numMoves);

k_r[8] = -1, -1, -1, 0, 1, 1, 1, 0
k_c[8] = -1, 0, 1, 1, 1, 0, -1, -1

l_r[8] = -2, -2, -1, 1, 2, 2, 1, -1
l_c[8] = -1, 1, 2, 2, 1, -1, -2, -2

dfs(n, r, c, size, start, numMoves)
    if r < 0 || r >= size || c < 0 || c >= size
        return 0

    if n == numMoves
        if r == start[0] && c == start[1]
            return 1
        else
            return 0

    long long ret = 0

    for i=0  i<8  i++
        ret += dfs(n+1, r+k_r[i], c+k_c[i], size, start, numMoves)

    for i=0  i<8  i++
        ret += dfs(n+1, r+l_r[i], c+l_c[i], size, start, numMoves)

    return ret

마지막 예제 시간초과

모든 경우를 깊이우선탐색 해서일까, 마지막 예제가 2초를 넘긴다

생각의 변화

전체 경우를 깊이 우선 탐색하면 호출스택이 너무 깊어진다

for loop 으로 대체

각 스탭별로 히스토리가 필요 자연스러운 구조

중복되거나 어색하지 않은

좌표 필요 move 도 필요

3차원 배열 이제 이 좌표에 올때 얼마나 걸렸는지 걸린 거리별로 히스토리가 구분된다 good

시작 위치가 (0,0) 이 아니면?

상관없다 진짜 괜찮나?...

맨 위에서 numMoves 만큼 도니까 괜찮다

더해야 한다 +=

pseudo code

move_r[16] = -1, -1, -1, 0, 1, 1, 1, 0, -2, -2, -1, 1, 2, 2, 1, -1
move_c[16] = -1, 0, 1, 1, 1, 0, -1, -1, -1, 1, 2, 2, 1, -1, -2, -2

long long ways[100][100][51]

howMany(size, start, end, numMoves)
    ways[start[0]][start[1][0] = 1

    for i=1  i<=numMoves  i++
        for r=0  r<size  r++
            for c=0  c<size  c++
                for j=0  j<16  j++
                    nr = r + move_r[j]
                    nc = c + move_c[j]

                    if (nr < 0 || nr >= size || nc < 0 || nc >= size)
                        continue

                    ways[nr][nc][i] += ways[r][c][i-1]

    return ways[end[0]][end[1]][numMoves]

삶을 이끄는 것은 무엇일까

어쩌면 그것이 사람을 만드는 것일테다 강물이 하구의 모양을 만들듯이

주인공은 자신의 마음이 이끄는 곳으로 향했고 지상에 도착한다

배신과 협잡, 생존과 야망만이 존재하는 어두운 세계를 뒤로하고

그렇게 도착한 곳에서 주인공은 피슬다운 가문을 만나게 된다

그들을 먼 발치에서 지켜보며 어쩌면 이곳이 자신의 집이 될수 있지 않을까 희망을 품어보았다

집, 마음이 거하는 곳 삶의 원칙을 지키며 살아갈수 있는 곳 가치있는 일을 할수 있는 곳 존중하는 친구들과 더불어 살수 있는 곳

그렇기에 주인공은 피슬다운 가문에 닥친 비극에 괴로워할수 밖에 없었던 걸테다

자신이 그토록 잊고자 했던, 피와 어둠이 자신을 따라온듯 해서

친구들이 겪은 비극에 대한 복수, 아니 어쩌면 속죄를 마치고 만신창이가 된 몸과 마음을 이끌고 나오지만, 그를 반기기라도 하듯 계속 인간과 괴물들이 뒤를 쫓아오게 된다

추적을 물리치고 다시 길 위에 섰을때 주인공은 생각했을지도 모른다

이번에는 집을 그리 쉽게 바라지 않겠다고

그 길이 어디로 이끄는지 알지 못한체

먼 길을 걸어 숲과 시내가 어우러진 곳에 임시거처를 마련한 주인공은 더이상 누구에게도 말을 걸지 않고 조용한 하루를 보내고 있었지만,

그런 그에게 이번엔 자연이 말을 걸어온다

'따뜻한' 땅위세계의 겨울을 체험하면서 그는 자연의 잔혹함과 아름다움을 그리고 자신의 유약함과 강인함을 알게 된다

그리고 그런 그에게 약속이라도 한듯 Mooshie 가 찾아오게 된다

이미 집에 대한 마음을 감추고 억눌러둔 주인공에게 Mooshie 의 초대는 뜻밖의 길로 그를 인도하게 된다

자신이 걸어온 어두운 길, 그 길에서 나오게 한 존재에 대해

자신의 마음, 그 마음의 이름에 대해 그리고 그걸 축복이라 부를지 괴로움이라 부를지에 대해서도

Mooshie 가 알려준 수많은 지식들은 주인공이 삶의 계절을 이해하고 자신의 삶을 좀더 풍부하게 할수 있게 하였고

무엇보다 Mooshie 가 알려준 삶의 온기는 주인공이 상처를 잊고 자신의 길을 걸을수 있게 해주었다

어쩌면, 그렇기에 Mooshie 는 주인공에게 대답을 받으려 했던걸지도 모른다

자신이 떠나고나면, 꼭 내가 했던 얘기를 떠올려보라고

주인공에게는 아직 남은 날이 많다고, 세상은 고통스러운 곳이기도 하지만 동시에 우리를 예상치못한 만남으로 이끄는 신비로운 곳이라는 걸

운명은 이번에도 주인공을 따라잡았고, 마치 주인공의 대답을 확인이라도 하려는듯, 오크왕과 와르그왕이 이끄는 군대는 Mooshie 의 숲을 습격한다.

불가능할꺼라 생각했지만, Mooshie 와 주인공은 그들을 물리쳤고, 그 과정에서 주인공은 소중한 친구를 잃게 된다.

그렇게 주인공은 운명에게 답을 했고, Mooshie 의 숲을 뒤로한체 수도자 무리에 합류해 다시 길을 떠나게 된다.

그들은 주인공에게 안전한 여행길을 제공했지만, 주인공과 다른 마음을 가진, 다른 신을 섬기는 자들이였다.

고행을 바라며 신을 섬기지만, 그 과정에서 자기에게 주어진 삶을 외면하는 이 자기를 잃고, 절제를 잃고, 그 빈자리를 술과 게으름이 차지하는 자

주인공은 다음 목적지를 끝으로 그들 곁을 떠나기로 한다

하지만, 예상치 못한 일로 갱도에 갇히게 되고, 주인공은 기지를, 어쩌면 만용을 발휘하여 레드 드래곤의 레어로 들어가게 된다.

Mooshie 가 알려준 지식, 그리고 드래곤처럼 생각하는 걸 통해, 레드 드래곤의 빈틈을 만들어 낸 주인공은, 결국 갱도를 탈출하는데 성공한다.

수도자들의 감사와 작별인사를 받으며, 주인공은 그들에게서 추방자들이 모인다는, 북쪽지역의 ten town 을 소개받는다.

일말의 기대를 품고 말을 달려 그곳에서 향했지만, 주인공은 다시 차가운 현실을 마주하게 되고, 시장의 배려로 icewind dale 이라는 근처 설산의 레인저 자리를 대신 소개받는다.

어쩌면 주인공은 조금 지쳐있던걸수도 있겠다는 생각이 들었다.

자신은 나쁜 drow 가 아니라는걸, 항상 증명해야 하는 삶. 그리고 그걸 증명한다 해도, 결국 운명의 장난에 의해 다시 손에 칼을 들고 피를 묻히고 그곳을 떠나야 하는 삶에 대해

그래서일까, 어쩌면 설산에 홀로있던 주인공은 설산에서의 삶을 긍정하지도 부정하지도 않았을것 같다. 대화할 상대는 없지만, 그래도 이제는 자신이 틀리지 않았다는건 이미 충분히 알고 있기에

Mooshie, Clacker, Belwar, 더이상 만날수 없지만 이미 주인공의 마음속에 함께하는 이들, 그들과의 시간을 기억하고 있기에

그렇게 설산에서의 조용한 시간을 보내던 주인공에게, Gunevwar 를 쫓아온 한 소녀가 불현듯 찾아오게 된다.

당차고 호기심많은 그 소녀는 처음엔 경계했지만, Gunevwar 를 쓰다듬으며 조금씩 거리를 좁힌 둘은 이내, 자신들이 살아온 세상에 대해 얘기하게 된다.

그렇게 새로운 친구를 사귄 주인공은 생각하지 못했을 것이다. 그를 오랫동안 '찾아온' 존재가 곧 그를 만날것이라는 걸

피슬다운가의 비극이 있었을때, Maldobar 의 시장은 한 현상금 사냥꾼에게 drow 사냥을 의뢰했었고, 그 현상금 사냥꾼은 주인공에게 자신의 개 두마리중 하나를 잃고, 얼굴에 큰 흉터까지 받으면서 자존심에 큰 상처를 입은 상태였다

이후 그는 집요하게 주인공을 쫓았고, 주인공은 몰랐지만 주인공이 겪었던 사건들의 배후에는 항상 이 현상금 사냥꾼이 존재했다

현상금 사냥꾼은 마침내 주인공을 찾고 공격하지만, 주인공은 반격하지 않는다 제풀에 지쳐쓰러지기를 기대했던 거지만, 오히려 상황은 점점 위험하게 변해간다

Gunevwar 가 공격당했을때 주인공은 마침내 공세로 바꾸게 되고, 현상금 사냥꾼을 제압하지만 그 과정에서 현상금 사냥꾼은 알게 된다. 주인공은 자신을 죽이지 '못한다' 는걸

자신을 죽이지 않으면, 끝까지 쫓아가겠다는 도발을 들으며 주인공은 흔들린다.

주인공도 알고 있었던 것이다. 그를 죽이는게 '편리' 하다는걸

하지만, 마지막 순간 그는 스스로에게 'No' 라고 외쳤고 현상금 사냥꾼을 기절시키고 그 자리를 떠나게 된다

주인공은 자신의 거처로 돌아오고, 짐을 챙기기 시작했다 그의 마음은 지쳐있었고, 이유없는 적의에 맞서 칼을 드는 일. 그 일의 지난함을, 알게 된걸수도 있다.

'Drizzit', 그 단어를 중얼거리는 모습을 보며

집을 찾는 것, 집을 찾겠다는 마음, 어쩌면, 불가능한 걸 바라는 마음인걸까. 라는 무거운 생각이 그의 마음을 짓누르는 듯 햇다.

그렇게, 앞으로 더 길어질 길을 재촉하며 거처를 나온 주인공의 앞에 처음보는 드워프 한명이 앉아있었다.

그 드워프는 소녀의 아버지였고, 이 설산에 있는 드워프들의 왕이였다 그는 자신의 딸을 위협했던 현상금 사냥꾼을 직접 '상대' 했고 그 현상금 사냥꾼이 떠날수 밖에 없게 만들었다

현상금 사냥꾼을 제압하고, 그가 아끼는 동료, 남은 개의 다리 한짝을 잘라서 구워먹어 버린 것이다

무뚝뚝하고 완고한 드워프는 자신이 한일을 명료하게 말해주진 않았지만 적어도 그 드워프는 주인공에게 2가지를 알려주었다.

이름은 무엇을 붙이던 이름일 뿐이고, 그 본질은 달라지지 않는다는 것

그리고 무엇보다, 주인공은 자신도 모르는 사이에 갖게 된것이다 집, 이라 부를 수 있는 장소를

영작

What leads one's life?

Perhaps it makes oneself like river flow makes estuary

Our protagonist move ahead the place where his heart leads and reach the surface.

Behind the dark realm only treachery, scheme, survival and ambition resides.

At the surface, He first met Fissledown family.

Watching them at a distance, He hoped perhaps this place could be his home.

Home, where heart resides Place where one can live in accordance with one's principle of life. Place where work can have meaning and value. Place where one live with friends one can respect.

and that's why our protagonist feel guilt for the tragedy of fissledown family.

Blood and darkness, which he so dearly cast away, and yet follow him.

He finishes the revenge of the tragedy his friends went through. Perhaps it not revenge, more like atonement.

In tattered both body and soul, He move out, but more humans and monsters keeps come after him, as if they truly welcoming him.

After defeat the chase, He stood again at the road and might think, this time, he would not hope for home so easily.

Although he doesn't know what the path will lead hime.

He walks long roads. and found place to stay for the time being where forest meets the stream.

He spent quiet day, no more talk to anyone, perhaps himself.

His solitary days ended when nature talk to him.

Experiencing winter of 'warm' surface world, He come to know nature's harshness and beauty, and his own weakness and strength.

After winter, An old man named Mooshie came to him, as though they agreed.

Our protagonist who already hide and surpress his heart for yearning home, unexpectedly was led the path that Mooshie's invitation guides.

Mooshie tells him many things, his heart, its name and whether one should call this blessing or torment

That knowledge both enrich his life and know the life's season.

and most of all, the warmth that Mooshie taught him made our protagonist walk his own path, leaving his bitter past behind.

maybe that's the reason why Mooshie wanted his answer.

He should recall the word that Mooshie once told.

He has many days to live, although world is a painful place, also it is a enchanting place that guides unexpected encounter.

Fate caught up with him once again.

Orc king and Warg king storm the Mooshie's forest as if checking our protagonist's answer.

Although seems impossible, Mooshie and our protagonist defeat them, but in the process, he lost his dear friend, Mooshie.

Thus, the protagonist answered the fate. left Mooshie's forest behind, he set out on the road again with Friar company.

They provide safe journey, but have different heart, serving different god.

The one is yearning torment, worshipping god, but turn away from one's life The one is losing himself, losing control, and endurge with drink and laziness.

Our protagonist decide to leave them at the next destination.

but in unexpected events, they trapped in a mine shaft. And usnig his wit, perhaps recklessness and foolhardiness, They entered the lair of a red dragon.

Our protagonist created a gap using Mooshie's knowledge and thinking like dragon, Eventually escape the red dragon's lair.

Receiving both gratitude and farewell, Our protagonist headed north, ten town where ourcasts gathered.

Harbor a faint hope, He rode there on horseback, but met with harsh reality again. Instead, he is introduced a position of ranger in icewind dale, nearby snowy mountain.

Perhaps Our protagonist might felt tired

Tired of life that always proving i'm not a evil drow. And if proving it, eventually a twist of fate made him hold the scimatar and leave the place with bloodied hand.

maybe that's the reason, He neither affirm nor deny this life in snowy mountain. Although solitude is his only companion, He know his life is not wrong fully well.

In his heart, Mooshie, Clacker, Belwar, although no longer met, remain his side, and cherish the time they shared.

An encounter with a girl follow Gunevwar suddenly break his quiet time.

A spirited and curious girl remain vigilant at first, but petting Gunewvar, they gradually get closer.

They share talks about a world they had lived.

At that time, our protagonist could not think. An entity searching for him so long, finally appear before him.

When the tragedy of fissledown family, the mayor of Maldobar hire a bounty hunter for drow, and in process bounty hunter lost one of his dog and get scar on his face by our protagonist, which made his pride seriously injured.

After that, He persistantly followed our protagonist, and he was always behind all incidents that our protagonist went through.

Finally bounty hunter found our protagonist and attacked him, but our protagonist didn't fight back, hoping to collapse from his own exhaustion.

But situation becomes dangerous.

When Gunevwar attacked by the bounty hunter, our protagonist finally went on the offensive, subdue bounty hunter. But in the process, bounty hunter know that our protagonist cannot kill him.

In continous instigation from bounty hunter, our protagonist faltered.

He also knew that killing him is 'convenient'

But, at the final moment, he shout to himself 'No' and leave the place with stunned bounty hunter.

Returned his shelter, Our protagonist packed his belongings, knowing hardship of remain defiant toward unjustified hostility.

Muttered the word, 'Drizzit'

it weighted heavily on his heart of the thought. the thought that finding home, the heart that yearning of impossible thing.

And so, hasting the path that will get longer, Our protagonist went out the shelter and saw a unknown dwarf sitting right in front of him of rock pile.

That dwarf is a father of the girl, and king of this snowy mountain. He confonted the bounty hunter who threaten his daughter, and make him leave the mountain.

In front of sudbued bounty hunter, He cut off the leg of hunter's dog, and eat it.

Gruff and stubborn drawf didn't tell what exactly he did. But He imply two things to our protagonist.

Name is just a name. whatever it named on a thing, it's true nature never changes.

and most of all, our protagonist unknowingly have the place.

the place he can call, a home.

첨삭버전

What leads one's life?

Perhaps it shapes oneself, like a river's flow shapes an estuary.

Our protagonist moves toward the place where his heart leads and finally reaches the surface.

Behind the dark realm, only treachery, schemes, survival, and ambition reside.

At the surface, he first meets the Fissledown family.

Watching them from a distance, he hopes that perhaps this place could be his home.

Home — where the heart resides. A place where one can live according to one's principles. A place where work has meaning and value. A place where one can live with friends one can respect.

And that is why our protagonist feels guilt over the tragedy of the Fissledown family.

The blood and darkness he so dearly tried to cast away still follow him.

He finishes avenging the tragedy his friends endured. Perhaps it is not revenge, but atonement.

In tattered body and soul, he moves on, but more humans and monsters continue to come after him, as if truly welcoming him.

After defeating the chase, he stands on the road again, and might think: this time, he would not hope for home so easily.

Although he does not know where the path will lead him, he walks long roads and finds a place to stay for the time being, where the forest meets the stream.

He spends quiet days, speaking to no one, perhaps only to himself.

His solitary days end when nature begins to speak to him.

Experiencing the winter of the 'warm' surface world, he comes to know nature's harshness and beauty, and discovers both his own weakness and strength.

After winter, an old man named Mooshie comes to him, as though by mutual agreement.

Our protagonist, who has already hidden and suppressed his yearning for home, unexpectedly is led along the path that Mooshie's invitation guides.

Mooshie teaches him many things: about his heart, its name, and whether to call it a blessing or a torment.

That knowledge both enriches his life and teaches him the seasons of life.

And most of all, the warmth Mooshie imparts allows our protagonist to walk his own path, leaving his bitter past behind.

Perhaps that is why Mooshie sought his answer.

He must recall the words Mooshie once told him: he has many days to live, and although the world is painful, it is also an enchanting place, guiding unexpected encounters.

Fate catches up with him once again.

The Orc King and Warg King storm Mooshie's forest, as if testing our protagonist's answer.

Although it seems impossible, Mooshie and our protagonist defeat them. But in the process, he loses his dear friend Mooshie.

Thus, the protagonist answers fate. Leaving Mooshie's forest behind, he sets out on the road again with the Friar company.

They provide a safe journey, but their hearts differ, serving different gods.

One yearns for torment, worshipping a god, yet turns away from life itself. The other loses himself, succumbs to drink and laziness.

Our protagonist decides to leave them at the next destination.

But in an unexpected turn, they are trapped in a mine shaft. Using his wit, and perhaps a touch of recklessness, he leads them into the lair of a red dragon.

Our protagonist creates an opening using Mooshie's knowledge, thinking like a dragon, and eventually escapes the lair.

Receiving both gratitude and farewell, he heads north to Ten Towns, where outcasts have gathered.

Harboring a faint hope, he rides there on horseback, but meets harsh reality again. Instead, he is introduced to a position as a ranger in Icewind Dale, near the snowy mountains.

Perhaps our protagonist feels tired — tired of a life constantly proving he is not an evil drow. And when he does prove it, fate twists, forcing him to take up the scimitar and leave with bloodied hands.

Perhaps this is why he neither affirms nor denies life in the snowy mountains. Although solitude is his only companion, he knows his life is not entirely wrong.

In his heart, Mooshie, Clacker, and Belwar — though no longer present — remain by his side, cherished in memory.

His quiet days are suddenly interrupted by a spirited girl, she remains cautious at first, but gradually warms up as they bond over his pet, Gunevwar.

They share talks about the world they have lived in.

At that moment, he cannot anticipate the arrival of an entity searching for him so long — finally appearing.

During the Fissledown tragedy, the mayor of Maldobar hired a bounty hunter to track a drow. In the process, the hunter lost one of his dogs and received a scar from our protagonist, wounding his pride.

Since then, he persistently followed the protagonist, always appearing behind every incident.

Finally, the bounty hunter confronts our protagonist. He does not fight back, hoping exhaustion will defeat him.

But the situation turns dangerous.

When Gunevwar is attacked, he goes on the offensive, subduing the hunter. In the process, the hunter realizes our protagonist cannot kill him.

Through continuous provocation, our protagonist falters, knowing that killing him would be 'convenient.'

But in the final moment, he shouts to himself: "No," and leaves, leaving the bounty hunter stunned.

Returning to his shelter, he packs his belongings, understanding the hardships of remaining defiant against unjust hostility.

Muttering the word, "Drizzt," it weighs heavily on his heart — the thought of finding home, the heart yearning for the impossible.

Thus, hastening along the path that stretches longer, he leaves the shelter and sees an unknown dwarf sitting atop a rock pile.

The dwarf is the girl's father, and king of the snowy mountain. He confronts the bounty hunter who threatened his daughter, forcing him to leave.

In front of the subdued hunter, he cuts off the leg of the hunter's dog — and eats it.

Gruff and stubborn, the dwarf does not say outright, but implies two things to our protagonist:

A name is just a name; whatever it is called, its true nature does not change.

And most of all, our protagonist unknowingly has a place — the place he can finally call home.

모든 마을 사람들은 자신의 양 옆에 있는 이웃을 싫어합니다

마을은 우물을 기준으로 원형으로 구성되어 있으며 시계방향으로 돌며 우물수리를 위해 마을 사람 i 는 donations[i] 만큼 기부하려 합니다

이때 이웃이 기부를 하면 자신은 기부하지 않습니다

donations[] 의 시작과 끝은 서로 이웃이며 donations[] 는 240개의 요소를 갖고, 각 요소는 11000 사이의 값입니다

마을에서 얻을 수 있는 가장 큰 기부금액을 리턴한다

예시 입력

1)
10, 3, 2, 5, 7, 8

2)
11, 15

3)
7, 7, 7, 7, 7, 7, 7

4)
1, 2, 3, 4, 5, 1, 2, 3, 4, 5

5)
94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74,
29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72

예시 출력

19
15
21
16
2926

생각의 변화

10을 선택하면 다음은 2또는 5이다

이분탐색이 가능해 보인다

홀수개라면

dfs 는 이후 선택지를 들고있어야 select[] 를 인자로 받는다

선택정보도 전달해야 하므로 i 를 인자로 받는다

select[] 는 0으로 초기화 한다

dfs 종료조건은 i >= n 로 해서 select, donations 의 inner product 값을 리턴

i+2 와 i+3 을 선택

round 연산 필요

양옆을 체크하는 식

round 연산을 쓰면 dfs 종료조건으로 i >= n 은 부자연스러운듯 하다

select 가 잘못 들어간다면 if 에서 inner product 값을 리턴하면 안된다

dfs 종료조건은 제거 언젠가는 select 에 넣을수 있는 1이 다 되어, 양옆 체크조건을 충족불가하여 inner product 값이 리턴될 것

잘못 들어갈일이 없게 미리 select 로 양옆 체크하고, dfs 를 호출한다 이후, dfs 내에서 select[] 세팅

pseudo code

maxDonations(donations)
    n = donations.size()

    vector<int> select(n, 0)

    ret = 0

    for i=0  i<n  i++
        ret = max(ret, dfs(i, select, donations, n)

    return ret


dfs(i, select, donations, n)
    ret = inner_product(select.begin(), select.end(), donations.begin(), 0)

    if (select[i] == 1)
        return ret

    select[i] = 1

    res2 = 0, res3 = 0

    if (select[i+2-1 % n] == 0  &&  select[i+2+1 % n] == 0)
        res2 = dfs(i+2 % n, select, donations, n)

    if (select[i+3-1 % n] == 0  &&  select[i+3+1 % n] == 0)
        res3 = dfs(i+3 % n, select, donations, n)

    ret = max(ret, res2)
    ret = max(ret, res3)

    return ret

마지막 예제 시간초과

2초 시간조건을 고려해야 한다

생각의 변화

시간을 줄이려면 dp[] 를 메모해둬야 한다

메모해둘 내용은 dp[i] : i 까지 고려했을때 최대값

'i 까지 고려했을때' 문장이 성립하려면 원형으로 돌며 탐색하기 보다, 선형으로 탐색할수 있어야 한다 (구체적으로는, 다른 인접조건을 고려하는것 없이 0번 원소부터 탐색할수 있게)

선형으로 탐색할수 있게 경우를 나눈다

0번 원소를 선택한 경우

• [2..n-2]

0번 원소를 선택하지 않은 경우

• [1..n-1]

이렇게 2개의 선형탐색 구간이 나온다

이후 각 선형탐색 구간에 대해 다음의 점화식을 적용해본다

dp[i] 값을 메모할때 i번 원소를 선택한 경우

• dp[i-2] + num[i]

i번 원소를 선택하지 않은 경우

• dp[i-1]

두 경우중 큰 값이 dp[i] 가 된다

이후 dp[n-1] 을 리턴

pseudo code

maxDonations(donations)
    n = donations.size()

    if n == 1
        return donations[0]


    vector<int> case1(donations.begin(), donations.end() - 1)
    vector<int> case2(donations.begin() + 1, donations.end())

    return max(checkLinear(case1), checkLinear(case2))

checkLinear(numbers)
    n = numbers.size()

    if n == 1
        return numbers[0]

    vector<int> dp(n, 0)

    dp[0] = numbers[0]
    dp[1] = numbers[0] > numbers[1] ? numbers[0] : numbers[1]

    for i=2  i<n  i++
        dp[i] = max(dp[i-2] + num[i], dp[i-1])

    return dp[n-1]    

각 직원은 여러명의 직접적인 매니저나 부하직원을 가질수 있다

부하없는 직원의 급여는 1 부하있는 직원의 급여는 직접적인 부하들 급여의 합이 된다

string[] relations 가 주어질때

relations[i] 의 j 번째 값에 따라 다음 관계가 성립한다 Y : 직원 i 가 직원 j 의 매니저이다 N : ... 가 아니다

배열은 1~50개 요소로 이루어져 있으며, 문자열은 요소수와 같은 길이이다

모든 직원의 급여 합계를 리턴한다

예시 입력

1)
"N"

2)
"NNYN",
"NNYN",
"NNNN",
"NYYN"

3)
"NNNNNN",
"YNYNNY",
"YNNNNY",
"NNNNNN",
"YNYNNN",
"YNNYNN"

4)
"NYNNYN",
"NNNNNN",
"NNNNNN",
"NNYNNN",
"NNNNNN",
"NNNYYN"

5)
"NNNN",
"NNNN",
"NNNN",
"NNNN"

예시 출력

1
5
17
8
4

생각의 변화

순서대로 본다면

아니면 아래에서 올라가는 것

다른 직원의 salary 를 보게 하려면

문자열 스캔결과를 [][] 에 저장할까, 저장할 값은 금액으로

아니다, 의존성 있는 직원이 먼저 나오면 순서대로 + [][] 스캔은 의미가 없다

Y 면 깊이우선 탐색

dfs() 에 인자로 문자열 index 를 넘길까

사이클이 생길수 있지 않을까 no. 무조건 최하급직원은 있을 것

그리고 탐색시 그 직원을 만날것 적절히 호출순서를 쌓는다면 리턴(종료) 가 보장

최하급직원을 어떻게 구할까

NNNNNN 부터 구하고 NNNNNN 의 직속상사를 구하고 그 직속상사들의 직속상사를 구한다 직속상사가 없을때까지 반복

N의 갯수(n) 를 dfs() 에 인자로 넘길까

"N" 1개만 있는 경우엔 N의 갯수로 dfs base 조건을 지정하면 어색하다

다른 n을 여기서도 쓰면 x n은 독립적이여야 함

직원 idx 도 인자에 주어 dp[] 활용할수 있게

테스트 하나 끝나면, dp[] 는 0으로 초기화 필요

pseudo code

long long dp[50]    // 0

totalSalary(relations)
    ret = 0
    i = 0

    for (auto &str : relations)
        ret += dfs(i, str, relations)
        i++

    return ret

dfs(idx, relation, relations)
    y_found = false

    for (auto &ch : relation)
        if ch == 'Y'
            y_found = true
            break

    if y_found == false
        return 1

    if dp[idx] != 0
        return dp[idx]

    i = 0
    ret = 0

    for (auto &ch : relation)
        if ch == 'Y'
            if dp[i] == 0
                dp[i] = dfs(i, relations[i], relations)

            ret += dp[i]

        i++

    return ret

베낭에 최대 10까지의 무게를 담을 수 있고

각 물건의 무게와 가치는 아래와 같다

물건    A    B    C    D    E
무게    3    4    1    2    3
가치    2    3    2    3    6

가치가 최대가 되게 담았을때의 가치를 리턴한다

예시 입력

0 0

예시 출력

14

생각의 변화

깊이우선탐색의 경우

w0 v0 인자로 현재 무게와 현재 가치

무게가 넘으면 리턴은 0

사용한 물건을 기록, 탐색끝나면 복귀

무게가 넘으면 리턴은 v

재귀식에 가치를 더해주는 과정이 들어가있다

value 가 max 인 값을 얻어야 한다

weight 가 초과되는 경우 value 를 그대로 리턴하려면

v 누적을 위해 ret 을 사용하였음

무게가 넘으면 -1 리턴 그러면 max 에서 자연스레 거를 것

pseudo code

struct stuff {
    int weight;
    int value;
};

vector<stuff> s = {
    {3, 2},
    {4, 3},
    {1, 2},
    {2, 3},
    {3, 6}
}

bool in_use[] = { false, false, false, false, false };

knapsack(w, v)
    if w > 10
        return -1

    i = 0
    ret = v

    for e : in_use
        if e == false
            in_use[i] = true
            ret = max(ret, knapsack(w + s[i].weight, v + s[i].value))
            in_use[i] = false

        i++

    return ret

응용 기술

메모화 재귀가 가능한 방식으로 탐색하는 방법도 있다

기존엔 현재 weight 와 value 를 전달했지만

현재 탐색길이와 weight 를 전달하는 방식을 사용하면, 별도로 in_use[] 를 기록해두지 않아도 되고, 메모화 재귀가 가능하다

탐색길이로 하면, 중간에 빠진 경우는 고려가 안되는것 아닌가 라는 생각이 들수있다

ex)
3,2 탐색하고
4,3 건너뛰고 1,2 탐색하려는 경우

하지만, 이 또한 knapsack2(n+1, w) 를 사용해 고려되어있다.

knapsack2(0, 0) 시작

knapsack2(0+1, 0+2) 탐색            // 3,2 탐색
knapsack2(0+1+1, 0+2) 탐색          // 4,3 건너뛰고
knapsack2(0+1+1+1, 0+2+2) 탐색      // 1,2 탐색

pseudo code

dp 를 -1 로 초기화 한후 수행하였다

int weight[5] = {3, 4, 1, 2, 3}
int price[5] = {2, 3, 2, 3, 6}
int maxw = 10

int dp[6][11]  // -1

knapsack2(n, w)
    if w > maxw
        return -1

    if n >= 5
        return 0

    if dp[n][w] >= 0
        return dp[n][w]

    ret = knapsack2(n+1, w)

    if w + weight[n] <= maxw
        val = knapsack2(n+1, w+weight[n])

        if val != -1
            ret = max(ret, val + price[n])

    return dp[n][w] = ret

응용기술

dp 를 활용해 계산하는 방법도 있다

총 무게와 몇 번째 물건까지 고려했는지를 dp[i][j] 로 나타내는 것이다

• 무게 : 가로 눈금
• 값 : 최대 가치합계

로직을 말로 쓰면 다음과 같다

caveat.
물건을 선택하지 않은 경우를 먼저 반영 (수직 화살표) 하고
이후 물건을 선택한 경우를 반영 (대각선 화살표) 한다

다음 행 값은 다음 행 값과 내 값(dp[i][j]) 중 큰 것

만약 현재 선택한 물건 무게가 눈금 내이면 다음 행 값은 다음 행 값과 내 값에 물건 가치를 더한 것(dp[i][j] + price[i]) 중 큰 것

caveat 에서 설명했듯이 dp의 경우 n[0..5] 로 진행하며 모든 경우를 체크하게 된다 여기에는 중간에 건너뛴 경우도 포함된다

pseudo code

dp 를 0 으로 초기화 한후 수행하였다

int weight[5] = {3, 4, 1, 2, 3};
int price[5] = {2, 3, 2, 3, 6};
int maxw = 10;

int dp[6][11];    // 0

knapsack(n, w)
    for i=0  i<5  i++
        for j=0  j<=maxw  j++
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])

            if j+weight[i] <= maxw
                dp[i+1][j+weight[i]] = max(dp[i+1][j+weight[i]], 
                                           dp[i][j]+price[i])

    ret = 0

    for k=0  k<=maxw  k++
        ret = max(ret, dp[5][k]

    return ret

숫자 4개가 적혀있는 카드가 있다

card 1 : 1 2 3 4 5 6 7 8
card 2 : 1 2 3 4 9 10 11 12
card 3 : 1 2 5 6 9 10 13 14
card 4 : 1 3 5 7 9 11 13 15

하나코는 카드를 보고 숫자 하나를 떠올린다

이후 각 카드별로 떠올린 숫자가 있는지 Y/N 로 알려준다

길이가 4인 문자열이 입력되면, 하나코가 머릿속에 떠올린 숫자를 interger 로 리턴한다

예시 입력

"YNYY"
"YNNN"
"NNNN"
"YYYY"
"NYNY"

예시 출력

5
8
16
1
11

생각의 변화

card mask 를 만들어 둔다

res = 0 을 두고, card 를 늘려가며 card mask 를 더해간다

• Y : res |= (mask[card])
• N : res &= ~(mask[card])

단순 비트연산으로는 부적절

N을 제외한 나머지 Y에서 모두 존재해야 한다

마지막 예제 NYNY 에서 11 대신 3이 나왔다

아.. 시작할때 N을 하면 &= ~() 할때 의미가 없구나

마지막에 N 을 수행하게 해야

한번 더

pseudo code

theNumber(answer)
    res = 0
    card = 0

    mask[] = {
        0x1fe, 0x1e1e, 0x6666, 0xaaaa
    }

    for (it = answer.begin()  it != answer.end()  it++)
        if (*it == 'Y')
            if (res == 0)
                res |= mask[card]
            else
                res &= mask[card]

        card++

    card = 0

    for (it = answer.begin()  it != answer.end()  it++)
        if (*it == 'N')
            res &= ~(mask[card])

        card++

    for (i = 0  i < 16  i++)
        if (res & 0x01)
            return i

        res = res >> 1

    return i

나무가 있으면 X, 지나갈수 있으면 . 로 된 미로가 있다.

현재 위치에서 움직일땐 moveRow, moveCol 에서 선택할수 있다

moveRow = { 1 0 -1 }
moveCol = { 3 -2 5 }

row col
(+1,-3)
( 0,-2)
(-1,+5)  중 하나를 선택해 이동

미로에서 나오지 못하게 하거나, 가능한 이동거리가 길어지게 미로를 설계하려 한다.

. 중 어떤 곳이던 출구를 놓는게 가능하다

미로를 빠져나오는 사람은 최단경로로 출구를 향해 간다

미로와 시작위치, moveRow, moveCol 이 주어질 때 최대 이동횟수를 리턴하고, 나올수 없는 경우 -1 을 리턴한다

예시 입력

1)
"...",
"...",
"..."

0, 1
{1, 0, -1, 0}
{0, 1, 0, -1}

2)
"...",
"...",
"..."

0, 1
{1, 0, -1, 0, 1, 1, -1, -1}
{0, 1, 0, -1, 1, -1, 1, -1}

3)
"X.X",
"...",
"XXX",
"X.X"

0, 1
{1, 0, -1, 0}
{0, 1, 0, -1}

4)
".......",
"X.X.X..",
"XXX...X",
"....X..",
"X....X.",
"......."

5, 0
{1, 0, -1, 0, -2, 1}
{0, -1, 0, 1, 3, 0}

5)
"......."

0, 0
{1, 0, 1, 0, 1, 0}
{0, 1, 0, 1, 0, 1}

6)
"..X.X.X.X.X.X."

0, 0
{2, 0, -2, 0}
{0, 2, 0, -2}

예시 출력

3
2
-1
7
6
-1

생각의 변화

벽, 제자리

queue 에 가능성 다 넣어두고 꺼내면서 체크

• queue<int,int>
• moveRow[i], moveCal[i]

넣는다, 꺼낸다, 벽이다/도착이다, 다시 넣는다 방문한 적이 있으면 . 를 v 로 하는 것에 대해 (visited)

queue 에서 꺼낸후 더 탐색을 해야할텐데, 다른 걸 먼저 진행 queue 대신 deque

근데 방문했다가 돌아다오면 이전 히스토리는 지워야 움직인 후에 돌아오는 것 음..

모든 . 를 v 로 바꾸는건 답이 될수 없음

exit 으로 가는 가장 긴 경로를 얻기 때문에 문제가 된다

모든 . 마다 도착가능한 최소경로를 획득

시작위치에서

1) 최단경로로 가장 멀리갈수 있는 경로 2) 접근 불가능한 . 가 있는지

최단경로 가장 멀리

내 좌표를 입력해야 할까 이동을 입력해야 할까

누적되어야 m 까지 같이, push

r, c, m push

이미 적었으니 대각선이 묻힐 이유는 없음 단지 더 큰 수라면

아트

X 에 대한 고려

pseudo code

struct rcm {
    int r;
    int c;
    int m;
};

longestPath(maze, startRow, startCol, moveRow, moveCol)
    r = startRow, c = startcol, m = 0

    vector<vector<int>> map
    map.resize(maze.size())

    for e : map
        e.resize(maze[0].size())

    queue<rcm> q

    q.push(rcm{r, c, m});

    while !q.empty()
        rcm p = q.front();
        q.pop();

        r = p.r
        c = p.c
        m = p.m

        if map[r][c] == 0
            map[r][c] = m
        else if map[r][c] > m
            map[r][c] = m

        for i=0  i<moveRow.size()  i++
            if (0 <= r+moveRow[i] < maze.size && r+moveCol[i]) && (0 <= c+moveCol[i] < maze[0].size())
                if map[r+moveRow[i]][c+moveCol[i]] == 0
                    if r+moveRow[i] == startRow && c+moveCol[i] == startCol

                    else
                        if maze[r+moveRow[i]][c+moveCol[i]] == '.'
                            q.push({r+moveRow[i], c+moveCol[i], m+1})

        res = 0

        for i=0  i<maze.size()  i++
            for j=0  j<maze[0].size()  j++
                if res < map[i][j]
                    res = map[i][j]

        r = 0
        c = 0

        for str : maze
            c = 0

            while (c = str.find('.',c)) != std::string::npos
                if map[r][c] == 0
                    if r == startRow && c == startCol
                    else
                        return -1

                c++
            r++

        return res