1. 도어맨굉장히 간단한 O(N) 그리디 풀이도 있는 거 같은데 난 잘 모르겠어서 DP로 해결했다. DP[i] = (1 ~ i번 사람이 모두 럽에 들어갔을 때 더 넣을 수 있는 사람의 수) 라고 정의하자. 두가지 케이스가 있다. * 첫번째 사람을 클럽에 영영 안 넣고 두번째 사람부터만 계속 추가. 이 방법으로 K명이 추가로 들어갔다면 DP[i] = K가 가능해진다. * 두번째 사람 이후를 K번 정도 더 넣고, 첫번째 사람을 추가. 차이에 문제가 생기지 않는다면 DP[i] = DP[i + K + 1] + K + 1가 가능해 진다. 모든 K에 대해서 대충 시뮬레이션한 후, 시뮬레이션 과정에서 문제가 없었으면 값을 갱신해주면 된다. 이런 식으로 DP 테이블을 채우면 DP[0]이 답이 된다. 잘 구현하면 O(N..
1. 지뢰찾기디스크립션에 매우 중요한 내용이 누락되어 있는데, 외곽선만 숫자가 공개되어 있으며 외곽선이 아닌 부분은 숫자가 전혀 써져있지 않다. 고로 외곽선과 붙어있는 영역에만 지뢰가 있을 수도 없을 수도 있는 것이고, 그렇지 않은 n-4 * n-4 영역에는 지뢰가 무조건 있다고 가정해도 된다. 최대화가 목표이기 때문이다. 외곽선과 붙어있는 영역의 지뢰를 최대화하라고 하지만, 사실 지뢰의 개수를 유일하게 결정할 수 있다. 모서리에 있는 지뢰를 제외한 모든 지뢰는 주위 3개의 셀에게 노출된다. 즉 모서리 지뢰를 제거하면 나머지 지뢰의 수는 적혀있는 숫자의 합 / 3 이라는 것이다. 모서리에 있는 지뢰는 모서리에 있는 숫자로 존재 여부를 결정할 수 있으니, 이를 결정하고 나머지 숫자의 합을 세주면 된다. n
1. Arrays 두 행과 열을 바꾼다는 것이 무슨 뜻인지 먼저 생각해 보자. 각각의 행과 열에 대해서 순열 P[i]와 Q[i]를 정의하자. P[i] = (현재 i번 행의 원래 위치), Q[i] = (현재 i번 열의 원래 위치) 라고 하면, 두 행을 바꾸는 것은 단순히 P[i]와 P[j]를 바꾸고, 열을 바꾸는 것은 단순히 Q[i]와 Q[j]를 바꾸는 것이다. 고로 우리가 주어진 연산으로 할 수 있는 것은 P와 Q를 임의의 순열로 섞는 것이니, A와 B가 닮았다 (alike) 는 것은 A[P[i]][Q[j]] = B[i][j] 를 만족하는 순열 P, Q가 존재한다는 것과 동치이다. 모든 수가 다르니, 각 수가 A에서 어떤 위치, B에서 어떤 위치에 있는지를 유일하게 결정할 수 있다. 즉 P[i] = j,..
- Total
- Today
- Yesterday