[C++] Samsung SW Expert Academy 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

/*

When I made 'check' as Map STL, it failed because it's too slow.
After I changed check to bool array, it got much faster.

It means that Map STL is sooooooooooo much slow.






*/

#include <iostream>
#include <string>

using namespace std;

bool check[100][999999]; //최대 교환 횟수를 100으로 가정함.
int max_num;

void calc(string num, int len, int change) {
    if(change==0) {   
        int result = stoi(num);
        max_num = max(max_num,result);

    } else {
        for(int i=0;i<len;i++) {
            for(int j=i+1;j<len;j++) {
                if(num[i] > num[j]) continue;
                char temp = num[i];
                num[i] = num[j];
                num[j] = temp;

                if(check[change-1][stoi(num)]) {
                    temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                    continue;
                } else {
                    check[change-1][stoi(num)] = true;
                    calc(num,len,change-1);
               
                    temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                }
            }
        }   
    }
}

int main() {
    int N;
    cin >> N;
   
    for (int i=1;i<=N;i++) {
    string num;
        int change;
        cin >> num;
        cin >> change;
        int len = num.size(); 
       
        max_num = 0;

calc(num,len,change);
       
       cout << "#" << i << " " << max_num << endl;
    }
   
return 0;
}

[C++] Samsung SW Expert Academy 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

/*

Basic DFS(or BFS) problem.






*/

#include <iostream>

using namespace std;

struct myPair {
int x;
    int y;
};
myPair comp,home;
myPair cust[10];
int result;
int visit[10];


int dist(myPair p1, myPair p2) {
int temp = abs(p1.x - p2.x);
    int temp2 = abs(p1.y - p2.y);
 
    return temp + temp2;
}

void dfs(int N, int prev, int cur, int sum, int count) {
    if(prev == -1) {
        sum = dist(comp,cust[cur]);
    }
    else {
        if (visit[cur] == 1) {
            return;
        }

        sum += dist(cust[prev],cust[cur]);
    }
 

    visit[cur] = 1;
    count++;
 
    if(count >= N) {
        sum += dist(cust[cur],home);
        result = min(result,sum);
        visit[cur] = 0;
        return;
    }
 
    for(int d=0;d<N;d++) {
    dfs(N,cur,d,sum,count);
    }
    visit[cur] = 0;

}

void calc(int N){
    for(int i=0;i<N;i++) {
        dfs(N,-1,i,0,0);
    }
}

int main() {
    int T;
    cin >> T;
 
    for(int k=1;k<=T;k++){
        int N;
        cin >> N;
     
        cin >> comp.x;
        cin >> comp.y;
        cin >> home.x;
        cin >> home.y;

        for(int i=0;i<N;i++){
        cin >> cust[i].x;
            cin >> cust[i].y;
        }
     
     
        for(int i=0;i<N;i++) visit[i] = 0;
        result = 2000000000;
     
calc(N);
     
        cout << "#" << k << " " << result << endl;
 
    }
return 0;
 
}

[C++] Samsung SW Expert Academy 1226. [S/W 문제해결 기본] 7일차 - 미로1

/*

I faced segmentation fault at first, because I made map as int (int map[16][16])
but the input text was actually too long, so I changed it to 'string' type.




*/

#include <iostream>
#include <string>

using namespace std;

struct dot  {
int x;
    int y;
};
dot startP,endP;
string map[16];
int visit[16][16];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int find_flag;

void calc(int cur_x, int cur_y) {
if(visit[cur_y][cur_x] == 1) return;
    else {
    visit[cur_y][cur_x] = 1;
        if(map[cur_y][cur_x] == '1') return;
        else if (map[cur_y][cur_x] == '3') {
            find_flag = 1;
            return;
        }
       
        for(int i=0;i<4;i++) calc(cur_x+dir[i][0],cur_y+dir[i][1]);
    }
}


int main() {
for(int k=1;k<=10;k++) {
        int n;       
    cin >> n;
       
        for(int j=0;j<16;j++) {
            cin >> map[j];
        for(int i=0;i<16;i++) {
                visit[j][i] = 0;
                if(map[j][i] == '2') {
                startP.x = i;
                    startP.y = j;
                } else if (map[j][i] == '3') {
                endP.x = i;
                    endP.y = j;
                }
            }
        }
       
       
        find_flag = 0;
    calc(startP.x,startP.y);
       
        cout << "#" << k << " " << find_flag << endl;
   
    }
    return 0;
}

[C++] Samsung SW Expert Academy 1767. [SW Test 샘플문제] 프로세서 연결하기

/*
reference: https://kimth1130cr.blog.me/221144277234

My own code has the same logic, but use vector instead of array.
However it has errors, so I refered to the above link.


*/

#include <iostream>

using namespace std;

struct myCore {
int x, y;
};
myCore core[12];
int map[12][12];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int N,core_count;
int core_max, line_min;

int cirsum(int cmap[12][12]) {
int result = 0;
    for (int i=0; i<N; i++) {
        for (int j=0;j<N;j++) {
            if (cmap[i][j] == 2) result++;
        }
    }
    return result;
}

//cnum : 현재 선택한 코어번호.
//core_cur : 현재 연결 성공한 코어 개수
void solve(int cnum, int cmap[12][12], int core_cur) {
if (cnum >= core_count) {
        if(core_cur > core_max) {
            core_max = core_cur;
            line_min = cirsum(cmap);
        }
        else if( core_cur == core_max) {
            line_min = min(line_min,cirsum(cmap));
        }
        return;
    }
 
    for (int d = 0; d<4; d++) {
    int cur_x = core[cnum].x;
        int cur_y = core[cnum].y;
        bool connect = true;
        int cnt = 0;
     
        while(1) {
        cur_x += dir[d][0];
            cur_y += dir[d][1];
            if (cur_x <0 || cur_x>=N || cur_y<0 || cur_y>=N)
                break;
            if(cmap[cur_x][cur_y] != 0){
                connect = false;
                break;
            }
            cmap[cur_x][cur_y] = 2;
            cnt++;
        }
        if(connect) {
        solve(cnum+1,cmap,core_cur+1);
        }
     
        cur_x = core[cnum].x + dir[d][0];
        cur_y = core[cnum].y + dir[d][1];   
        for(int i = 0; i<cnt; i++, cur_x+=dir[d][0],cur_y+=dir[d][1])
            cmap[cur_x][cur_y] = 0;
    }
 
    solve(cnum+1,cmap,core_cur);
 
}

int main() {
int T;
 
    cin >> T;
    for(int k=1; k<=T; k++) {
    cin >> N;
     
        core_count = 0;
        core_max = -1;
        line_min = 200;
        for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
                int input;
            cin >> input;
                map[i][j] = input;
             
                if(input == 1) {
                    if (i == 0 || i == N - 1 || j == 0 || j == N - 1)    continue;
                    else {
                        core[core_count].x = i;
                        core[core_count].y = j;
                        core_count++;                   
                    }

                }
            }
        }
        solve(0,map,0);
        cout << "#" << k << " " <<line_min << endl;
    }

 
    return 0;
}

[C++] Samsung SW Expert Academy 1206. [S/W 문제해결 기본] 1일차 - View

/*
This problem looks difficult first, but actually it's very simple.

Just check if current index is higher than both two sides.


*/


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int myView(int n, vector<int> arr);

int main() {
    int n,input;
    vector<int> arr;
for(int i=0;i<10;i++) {
    cin >> n;
        for(int j=0;j<n;j++) {
            cin >> input;
            arr.push_back(input);
        }
        int result = myView(n,arr);
        cout << "#" << i+1 << " " << result << endl;
        arr.clear();
    }
    return 0;
}

int myView(int n, vector<int> arr) {
  int leftMax, rightMax;
    int differ;
    int result = 0;
for(int i=2;i<n-2;i++) {
leftMax = max(arr[i-2],arr[i-1]);
        rightMax = max(arr[i+1],arr[i+2]);
        differ = arr[i] - max(leftMax,rightMax);
        if(differ > 0) {
        result += differ;
            i += 2;
        }
    }
   
    return result;
}