면빈면빈면빈면빈

[적용한 알고리즘]

브루트 포스, 재귀

[아이디어]

1. 한칸만 정하고 인접한 3칸만 이동하면 1가지 경우를 제외하고 전부 나타낼 수 있다.

2. 예외 케이스는 따로 처리해준다

[생각의 흐름 / 절차] 

1. 모양을 다해봐야하나? 너무 노가다여서 하기가 싫었다. 모양 간의 공통점을 찾고싶었다.

(ㅗ) 모양을 제외하면 나머지는 인접하게 붙은 4칸의 모양이었다. 

2. 경우의 수를 다 해봐야겠다. 한칸만 정하면 대부분의 경우의 수 표현가능,

나머지 한가지 (ㅗ,ㅜ,ㅓ,ㅏ) 모양은 따로 예외케이스 처리해서 빼줘야겠다.

3. 다음 칸으로 이동할때 dfs와는 동일하게 check 배열에 체크를 해주고,

재귀를 돌고 나올 때 check를 해제해줘야겠다.

-> 그래야 다른 점에서 시작하는 경우를 계산할 수 있으니까.

중복은 생기겠지만, 고려하지 않아도 된다. 어차피 최댓값만 구하면 되니까.

4. 모든 칸마다 반복문을 돌면서 실행해서 최댓값을 정해야겠다.

[교훈]

열심히 예외 케이스 처리하자. 이런 식으로 최대한 같은 걸로 묶고 예외로 빼줘야할 수도 있다. 

<코드>

#include <cstdio>
#include <algorithm>
#define SIZE 501
using namespace std;

int map[SIZE][SIZE];
bool check[SIZE][SIZE];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int n, m;
int ans = 0;

void tetrimino(int cnt, int curx, int cury, int sum){
    if (cnt == 4){
        ans = max(ans, sum);
        return;
    }

    if (check[curx][cury]) return;

    check[curx][cury] = true;

    for (int k = 0; k < 4; k++){
        int nx = curx + dirx[k];
        int ny = cury + diry[k];

        if (0 <= nx && nx < n && 0 <= ny && ny < m){
            tetrimino(cnt + 1, nx, ny, sum + map[curx][cury]);
        }
    }

    check[curx][cury] = false;
}

int tetrimino2(int curx, int cury){
    int ret = -1;
    int tempSum = 0;
    //세로 방향
    if (curx + 2 < n){
        tempSum = map[curx][cury] + map[curx + 1][cury] + map[curx + 2][cury];
        if (cury + 1 < m){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (cury - 1 >= 0){
            int temp = tempSum + map[curx + 1][cury - 1];
            ret = max(ret, temp);
        }
    }

    //가로 방향
    if (cury + 2 < m){
        tempSum = map[curx][cury] + map[curx][cury + 1] + map[curx][cury + 2];
        if (curx + 1 < n){
            int temp = tempSum + map[curx + 1][cury + 1];
            ret = max(ret, temp);
        }
        if (curx - 1 >= 0){
            int temp = tempSum + map[curx - 1][cury + 1];
            ret = max(ret, temp);
        }
    }

    return ret;
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            tetrimino(0, i, j, 0);
            ans = max(ans, tetrimino2(i, j));
        }
    }

    printf("%d\n", ans);
    return 0;
}

[적용한 알고리즘]

연산자 끼워넣기와 똑같다. 꽁문제 개이득ㅋ

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

내용

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
vector<int> res;

void go(vector<int> &arr, int idx, int cur, int pl, int mi, int mul, int div){
    if (idx == n){
        res.push_back(cur);
        return;
    }

    if (pl > 0) go(arr, idx + 1, cur + arr[idx], pl - 1, mi, mul, div);
    if (mi > 0) go(arr, idx + 1, cur - arr[idx], pl, mi - 1, mul, div);
    if (mul > 0) go(arr, idx + 1, cur * arr[idx], pl, mi, mul - 1, div);
    if (div > 0) go(arr, idx + 1, cur / arr[idx], pl, mi, mul, div - 1);
}

int main(){
    scanf("%d", &n);
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int oper[4];
    for (int i = 0; i < 4; i++){
        scanf("%d", &oper[i]);
    }

    go(arr, 1, arr[0], oper[0], oper[1], oper[2], oper[3]);

    int ans_min = 1000000005;
    int ans_max = -1000000005;
    for (int x : res){
        ans_min = min(ans_min, x);
        ans_max = max(ans_max, x);
    }

    printf("%d\n%d", ans_max, ans_min);
    return 0;
}

[적용한 알고리즘]

재귀, 브루트포스

[아이디어]

경우의 수를 세보니 다 해볼만 하더라.

[생각의 흐름 / 절차] 

다 해볼만 함 

필요한 인수 정리

제한 조건 써주기

[교훈]

재귀를 더 조져보자.

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
vector<int> res;

void go(vector<int> &arr, int idx, int cur, int pl, int mi, int mul, int div){
    if (idx == n){
        res.push_back(cur);
        return;
    }

    if (pl > 0) go(arr, idx + 1, cur + arr[idx], pl - 1, mi, mul, div);
    if (mi > 0) go(arr, idx + 1, cur - arr[idx], pl, mi - 1, mul, div);
    if (mul > 0) go(arr, idx + 1, cur * arr[idx], pl, mi, mul - 1, div);
    if (div > 0) go(arr, idx + 1, cur / arr[idx], pl, mi, mul, div - 1);
}

int main(){
    scanf("%d", &n);
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int oper[4];
    for (int i = 0; i < 4; i++){
        scanf("%d", &oper[i]);
    }

    go(arr, 1, arr[0], oper[0], oper[1], oper[2], oper[3]);

    int ans_min = 1000000005;
    int ans_max = -1000000005;
    for (int x : res){
        ans_min = min(ans_min, x);
        ans_max = max(ans_max, x);
    }

    printf("%d\n%d", ans_max, ans_min);
    return 0;
}

[적용한 알고리즘]

재귀

[아이디어]

다른 부분수열의 합과 동일

[생각의 흐름 / 절차] 

만들 수 있는 수들을 index 표시, 

반복문 돌면서 첫번째를 가져오면 될 것 같았다.

[교훈]

재귀를 더 연습하자.

직관적으로 와닿을 때까지.

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int arr[21];
bool check[20 * 100000 + 1];

void go(int index, int sum){
    if (index == n){
        check[sum] = true;
        return;
    }
    go(index + 1, sum + arr[index]);
    go(index + 1, sum);
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);

    bool flag = false;
    for (int i = 0; i < 20 * 100000 + 1; i++){
        if (check[i]){
            flag = true;
        }
        else {
            if (flag){
                printf("%d\n", i);
                break;
            }
        }
    }

    return 0;
}

[적용한 알고리즘]

재귀

[아이디어]

X

[생각의 흐름 / 절차] 

경우의 수가 2^n 개이고 n<20 이니까 일일이 다 해봐도 괜찮겠다.

[교훈]

재귀를 더 연습해보자

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int arr[20];
int ans;
int n, goal;

void go(int index, int sum){
    if (index == n){
        if (sum == goal){
            ans++;
        }
        return;
    }
    go(index + 1, sum + arr[index]); //부분 수열에 포함시키는 경우
    go(index + 1, sum); // 부분 수열에 포함시키지 않는 경우
}

int main(){
    scanf("%d %d", &n, &goal);

    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);
    if (goal == 0){
        ans--;
    }

    printf("%d\n", ans);

    return 0;
}

적용한 알고리즘 : 재귀

아이디어 : X

생각의 흐름 / 절차 : X

교훈 / 생각했던 점들 / 복기 :

뽑을 때 뽑지 않을 때를 각각 구분해서 재귀를 돌리자.

재귀는 사전 순을 나타낼 때 괜찮은 방법이다.

재귀가 약하니까 몇 문제 더 해봅시다.

<코드>

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

vector<int> lotto;

void solve(vector<int> &a, int index, int cnt){
    if (cnt == 6){
        for (int num : lotto){
            printf("%d ", num);
        }
        printf("\n");
        return;
    }

    int n = a.size();
    if (n == index) return;

    //index 번째 고름
    lotto.push_back(a[index]);
    solve(a, index + 1, cnt + 1);

    //index 번째 안고름
    lotto.pop_back();
    solve(a, index + 1, cnt);
}
int main(){
    while (true){
        int n;
        scanf("%d", &n);
        if (n == 0){
            return 0;
        }

        vector<int> a(n);
        for (int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        }

        solve(a, 0, 0);
        printf("\n");
    }
}