1번 문제

태그: 2차원 배열, 구현, 해시

티어: 실버1

1. 2차원 배열에 그림처럼 1 ~ N번 블록을 라벨링, 라벨링 도중에 현재 번호의 블록이 처음으로 출연하는 좌표도 저장해두자.

2. 2차원 배열 돌면서 각 블록에 대해서 상하좌우로 인접한 블록들의 개수를 세자. 이 때 해시를 이용하면 편하다. 다른 블록을 중복해서 세면 안되기 때문.

3. 1 ~ N번 블록에 대해서 해시 사이즈가 가장 큰 블록의 좌표들을 순서대로 모아서 리턴 (해시 사이즈가 결국 인접한 블록의 개수이기 때문)

2번 문제

태그: 백트래킹, 깊이 우선 탐색, 완전 탐색

티어: 골5

이 문제는 예제에 힌트가 있다. 모든 번호를 사용해서 경우의 수를 만들더라도 2e6인가 그정도밖에 안된다.

즉, 완전 탐색으로 모든 경우의 수를 세도 시간 제한이 널럴하다는 의미임.

처음에 조합론인 줄 알고 '미친 요즘 코테에 조합론도 나오나 조졌네' 생각했다가 예제보고 안심함.

그렇다면 4 x 3 크기의 핸드폰 입력창을 순회하면서 1일 때 백트래킹 함수 호출해서 경우의 수를 누적해주면 됨.

백트래킹 함수를 만드는 것도 쉽다. 상하좌우대각선 인접하면서 방문하지 않았었고 터치가 가능한 경우에 그 좌표로 또 재귀 호출해주면 된다.

이 때 깊이가 2이상일 때(연결된 숫자가 2개 이상)일 때만 ans++ 로 누적시키자.

구현해보니 개인적으로 난 2번이 1번보다 쉬웠음.

3번 문제

태그: 다이나믹 프로그래밍

티어: 골3

일단 m개의 랜덤박스를 배치하는 경우의 수만 해도 m!이라 완전 탐색은 말이 안된다. 이 경우엔 dp를 적용해볼 수 있음.

'dp[m][x][i] = m개의 랜덤 박스가 남았고 현재 슬라임의 번호가 x일 때, 마지막에 슬라임 i를 만들 수 있는 경우의 수' 라고 정의하자.

그러면 시간복잡도가 O(1e9)로 딱 1억이 나옴. 실제로 채점할 때 뒤에 갈수록 존나 느려서 시간 초과 나오는 줄 알았음...

코드는 올리면 안될 거 같고 어쨌든 저 dp식으로 재귀 계속 호출하면서 메모이제이션 하면 풀림.

4번 문제

1. select를 두 번 해준다. 

2. select한 두 개의 쿼리를 join 해주는데 서로 색깔이 다를 때 join이 되도록 해준다.

3. 이제 select 절에서 두 개의 색깔을 이용해서 카운팅을 해주면 된다.

총평

카카오 수준까진 아니긴 함.

근데 올솔할 정도면 카카오는 무난히 4.5솔 이상해서 합격할 확률이 높음.