원티드 쇼미더코드 3회차 후기

쇼미더코드라고 원티드에서 코딩테스트 대회라고 있다.
코테는 정말정말 오랜만이고, 감 측정 겸 해보기로 했다.

놀랍게도, 백준 기반 테스트였다. 매번 프로그래머스만 쓰다가 백준은 많이 오래 전인듯하지만..

문제는 그렇게 어렵지는 않았는데, 마지막 문제를 못 풀었다.

(C문제 풀기 위한 몸부림)

A: 신을 모시는 사당

Link

부분합 응용? 문제이다.

일단 이 문제가 부분합 문제라는 것을 인식하는 것이 첫 번째이고,
원본 배열을 어떻게 표현할 지 정해주는 것 까지 하면 OK

부분합 배열을 만들고 정렬해 가장 큰 값과 작은 값의 차가 답이다.

문제를 잘못 읽어서 조금 더 걸린 게 아쉬운 점. 17분 소요

n = int(input())
lst = list(map(int, input().split()))

lst2 = [0]
window_sum = 0
for i in range(n):
    if lst[i] == 1:
        window_sum += 1
    else:
        window_sum -= 1
    lst2.append(window_sum)

lst2.sort()
print(lst2[-1] - lst2[0])

B: 도넛 행성

Link

그래프 순회 기초 문제.

원래 이런 문제는 양쪽이 막혀 있었는데 도넛 모양으로 뚫어놓은 게 특징.
BFS로 각 영역 순회한 횟수를 구하면 된다. 15분 소요

n, m = map(int, input().split())
my_map = []
q = []
visited = [[0 for _ in range(m)] for _ in range(n)]
num_areas = 0

for i in range(n):
    my_map.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if my_map[i][j] == 0 and visited[i][j] != 1:
            q = [[i, j]]
            num_areas += 1

            while len(q) != 0:
                a, b = q[0]
                del q[0]

                if visited[a][b] == 1:
                    continue

                visited[a][b] = 1

                a_up = (a + n - 1) % n
                a_down = (a + n + 1) % n
                b_left = (b + m - 1) % m
                b_right = (b + m + 1) % m

                if my_map[a_up][b] == 0 and visited[a_up][b] != 1:
                    q.append([a_up, b])
                if my_map[a_down][b] == 0 and visited[a_down][b] != 1:
                    q.append([a_down, b])
                if my_map[a][b_left] == 0 and visited[a][b_left] != 1:
                    q.append([a, b_left])
                if my_map[a][b_right] == 0 and visited[a][b_right] != 1:
                    q.append([a, b_right])

print(num_areas)

C: 미팅

Link

오랜만의 DP 문제이고, $O(nm(n+m))$에서 못 줄이고 1시간 반만에 GG

이 블로그에서 풀이를 볼 수 있다.

n, m, c = map(int, input().split())
w_list = []
dp = [[-1 for _ in range(m)] for _ in range(n)]

for i in range(c):
    w_list.append(list(map(int, input().split())))

a_cond = list(map(int, input().split()))
b_cond = list(map(int, input().split()))

for i in range(n):
    a_cond[i] -= 1
for j in range(m):
    b_cond[j] -= 1

for i in range(n):
    dp[i][0] = w_list[a_cond[i]][b_cond[0]]
for j in range(m):
    dp[0][j] = w_list[a_cond[0]][b_cond[1]]

for i in range(1, n):
    for j in range(1, m):
        i1j1 = w_list[a_cond[i]][b_cond[j]] + dp[i - 1][j - 1]
        i0j1 = w_list[a_cond[0]][b_cond[j]]
        i1j0 = w_list[a_cond[i]][b_cond[0]]
        for k in range(1, i):
            i0j1 = max(i0j1, w_list[a_cond[k]][b_cond[j]] + dp[k - 1][j - 1])
        for k in range(1, j):
            i1j0 = max(i1j0, w_list[a_cond[i]][b_cond[k]] + dp[i - 1][k - 1])
        dp[i][j] = max(max(i1j1, i0j1), i1j0)


print(dp[n - 1][m - 1])

여기서 시간 초과가 나서 아 이건 언어 문제일 수도 있겠다 해서 C++로도 제출해보았다. (실제로 그렇게 해서 통과된 적이 있었기 때문)
근데 아니었고 같은 시간 초과

#include <iostream>
using namespace std;


long long max(long long a, long long b) {
	if (a > b) {
		return a;
	} else {
		return b;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

    int n, m, c;

    cin >> n >> m >> c;
    
    long long** w_list = new long long*[n];
    long long** dp = new long long*[n];
    
    for (int i = 0; i != n; ++i) {
    	w_list[i] = new long long[m];
    	dp[i] = new long long[m];
	}
	
	long long* a_cond = new long long[n];
	long long* b_cond = new long long[m];
    
    for (int i = 0; i != c; ++i)
        for (int j = 0; j != c; ++j)
            cin >> w_list[i][j];
    
    for (int i = 0; i != n; ++i) {
        cin >> a_cond[i];
        a_cond[i] -= 1;
    }
    for (int j = 0; j != m; ++j) {
        cin >> b_cond[j];
        b_cond[j] -= 1;
    }

    for (int i = 0; i != n; ++i) {
        dp[i][0] = w_list[a_cond[i]][b_cond[0]];
    }
    for (int j = 0; j != m; ++j) {
        dp[0][j] = w_list[a_cond[0]][b_cond[j]];
    }
    

    for (int i = 1; i != n; ++i) {
        for (int j = 1; j != m; ++j) {
            long long i1j1 = w_list[a_cond[i]][b_cond[j]] + dp[i - 1][j - 1];
            long long i0j1 = w_list[a_cond[0]][b_cond[j]];
            long long i1j0 = w_list[a_cond[i]][b_cond[0]];
            for (int k = 1; k != i; ++k) {
                i0j1 = max(i0j1, w_list[a_cond[k]][b_cond[j]] + dp[k - 1][j - 1]);
            }
            for (int k = 1; k != j; ++k) {
                i1j0 = max(i1j0, w_list[a_cond[i]][b_cond[k]] + dp[i - 1][k - 1]);
            }
            dp[i][j] = max(max(i1j1, i0j1), i1j0);
        }
    }

    cout << dp[n - 1][m - 1];
    
    for (int i = 0; i != n; ++i) {
    	delete[] w_list[i];
    	delete[] dp[i];
	}
	
	delete[] w_list;
	delete[] dp;
    
    
    return 0;
}

역시 DP는 어렵다.