2022 Dev-Matching: 게임 프로그래머 코딩테스트 후기

성과

 

총 3 문제 중 2문제를 풀 수 있었다. 

 

유형

 

1번 문제는 문자열 쪼개기와 단순 구현이었다. n월 n일을 1월 1일로부터 n일 이런식으로 바꿔주면서 해결해주었다.

 

2번 문제는 n목 만들기였는데 가로방향,세로방향,대각선 2방향으로 dp를 해줘서 각 방향으로 n목이 존재하는지 확인했다. 당연하게도 n목보다 n+1목의 개수가 많을 수는 없다. 또한 n+2, n+3목의 존재 여부는 아무 상관이 없다. n개가 이어진 것이 3개인데 n+1개가 이어진 것이 2개라면 3개의 n목중 2개는 무효가 되는 셈이니까, 따라서 만족하는 n목의 개수는 존재하는 n목의 개수에서 존재하는 n+1목의 개수를 빼 준 값이라 생각했다.

 

3번 문제는 사실 감이 잘 오지 않았다. 대략 10번 내의 이동으로 해결할 수 있을 것 같았지만 한번 이동에 경우의 수는 16 내가 짠 이동 방식이면 이동하는데도 16+@의 시간이 걸린다. 정말 드러운 시간복잡도가 나와서 Meet in the Middle을 이용해서 풀려해도 답이 나오지 않았다. 이전과 똑같은 상황이 나오지 않도록 / 이미 경험한 케이스면 스킵하도록 을 딕셔너리에 넣어 체크해주려 했는데 이것 또한 시간복잡도와 공간복잡도를 망치는데 일조한 것 같다. 아쉽게도 끝내 3번은 풀지 못하였다.

 

후기

무난무난하게 본 것 같다.

 

결과

1차전형에 합격했다!