[Codeground] S/W멤버십 3월 상시선발 S/W검정

기분이 좋으면서도 좋지 않은 삼성 소프트웨어 멤버십 3월 1차 시험이다.

3시간동안 풀어야 할 문제를 누군가는 15분도 되지 않아 푼 사람이 있었다.

(15분째에 내가 1번 문제를 해결했는데 2문제 모두 만점자가 존재했다.)

2월에 비해 3월은 매우 난이도가 낮았고, PS(해결 전략)만 제대로 눈치 챈다면 정말 10분만에도 풀 수 있는 것 같았다.

(삼성 S/W 멤버십 문제는 모두 저작권이 존재하고, 다시 풀 수 없으므로 링크가 없습니다.)

A. 자리 배치 

1번문제는 다음과 같다.

N*M 배열에 (0,0)와 (N-1,M-1)을 제외하고 2명씩 짝을 지을 때 최대로 많이 앉을 수 있는 수를 구해야 한다.

조건으로 짝은 앞,뒤,좌,우로 인접해 있어야 한다고 했다.

예를들어 

xooo

oooo

oooo

oooo

ooox

라는 5x4 배열이 있다면 최대 짝은 9이다.

이 문제는 알고리즘을 이용하여 문제 해결을 한다기 보단, 규칙을 찾는 것이 훨씬 좋은 것 같았다.

왜냐면 범위 자체도 2<= N,M <= 10000 이기에 DFS, BFS는 무리가 있어 보였고, 코드도 간결하지는 않을 것 같았다.

정답은 다음과 같다.

N, M이 홀, 홀일 경우 = (N*M)/2 - 1

N, M이 홀, 짝일 경우 = (N*M)/2 - 1

N, M이 짝, 짝일 경우 = (N*M)/2 - 2

규칙을 통해 발견한다면 시간복잡도는 O(1)로 해결이 된다.

아주 숏코딩 하기 좋은 코드이지만, 대회이기도 하고 가독성을 위해 숏코딩은 하지 않았다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <cstdio> #include <iostream>   using namespace std;   int main(int argc, char** argv) {     setbuf(stdout, NULL);       int T;     int test_case;       scanf("%d", &T);           for (test_case = 1; test_case <= T; test_case++)      {         int a, b;         int judge; // 1 :: 홀짝 2 :: 짝짝 3 :: 홀홀         int ans;         scanf("%d %d", &a, &b);           if (a % 2 == 1) // 홀         {             if (b % 2 == 1) // 홀홀                 judge = 3;               else // 홀짝                 judge = 1;         }           else // 짝         {             if (b % 2 == 1) // 홀짝                 judge = 1;               else // 짝짝                 judge = 2;         }           if (judge == 1)             ans = (a * b) / 2 - 1;           else if (judge == 2)             ans = (a * b) / 2 - 2;           else if (judge == 3)             ans = (a * b) / 2 - 1;             printf("Case #%d\n", test_case);         printf("%d\n", ans);       }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B. N*3 행렬 게임

2번 문제 또한 매우 쉬운 DP 문제중 하나였다. 

문제는 다음과 같다.

어떤 N*3 배열이 주어졌고, 모두 숫자로 배열이 차 있을 때, 행렬의 각 행마다 점수를 선택하여 만들 수 있는 최대치를 구해야 한다.

조건은 연속으로 같은 열은 선택 할 수 없고, 행마다 하나의 점수만 선택 할 수 있다.

예를들면

1 2 3

4 5 6

7 8 9

라고 주어졌을 때 

1 2 3

4 5 6

7 8 9

정답은 3 + 5 + 9인 17이 된다.

어느정도 알고리즘 문제를 푼 사람들이라면, DP로 매우 쉽게 해결 할 수 있는 문제이다.

소스 코드를 통해 확인하는 것이 설명으로 하는 것 보다 더 쉬울 것 같다.

시간 복잡도 :: O(N)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
int arr[1001][4];
int DP[1001][4];
 
int main(int argc, char** argv)
{
    setbuf(stdout, NULL);
 
    int T;
    int test_case;
 
    scanf("%d", &T);    
 
    for (test_case = 1; test_case <= T; test_case++) 
    {
        memset(arr, 0, sizeof(arr));
        memset(arr, 0, sizeof(DP));
 
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 3; j++)
                scanf("%d", &arr[i][j]);
 
        for (int i = 0; i < 3; i++)
            DP[0][i] = arr[0][i];
 
        int get; // 최댓값
 
        for (int i = 1; i < n; i++)
        {
            DP[i][0] = arr[i][0] + max(DP[i - 1][1], DP[i - 1][2]);
            DP[i][1] = arr[i][1] + max(DP[i - 1][0], DP[i - 1][2]);
            DP[i][2] = arr[i][2] + max(DP[i - 1][0], DP[i - 1][1]);
        }
 
        int ans = 0;
        for (int i = 0; i < 3; i++)
            ans = max(ans, DP[n - 1][i]);
 
        printf("Case #%d\n", test_case);
        printf("%d\n", ans);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

사실 아주 간단하다고 말은 하고 있지만, 시험 도중에 나도 DP인건 알고 있었어도, 결국 3중 포문으로 혼자 헛짓을 계속하고 있었다.

그러고는 잘 안풀리니 혼자 멍하게 있었던 시간이 있어서 아쉬웠다. 시험 시간 동안 너무 긴장하는게 아닌가 싶다.

다음 2차는 시험 난이도가 어떨지 궁금하기도 하며 더 유연하게 문제를 해결하고 싶다.