2839 설탕배달
2355 시그마
3108 로고
2186 문자판
1194 달이차오른다 가자
5214 환승
10875 뱀
1799 비숍
1600 말이 되고픈 원숭이
3190 뱀
12196 Tetris(small)
12197 Tetris(Large)
12100 2048(easy)
12094 2048(hard)
2839
3*a + 5*b = n을 성립하는 a, b값 중 a+b의 최소값.
2355
i<=a<=j를 만족하는 a의 합. i,j는 정수다.
3108
직사각형이 주어졌을 때 한붓그리기를 몇번을 해야하는가. 서로 독립인 덩어리의 개수를 세고 0,0을 포함하는게 있으면 -=1.
2186
여러가지 방법이 있겠지만 나는 문자판을 입력받고 key[0]값인 곳에서 key_index를 변화시켜가며 bfs를 돌렸다.
1194
n,m<=50이고 key가 a~f까지 6개이므로 50*50*2^6개밖에 안된다. key값을 bitmask로 체크하며 bfs하면 된다.
5214
하이퍼튜브는 해당 덩어리 안에 있으면 어디서 어디로든 cost가 1인 시스템이다. 해당 덩어리에서 가상 노드를 만들어 연결한다. 그 다음 bfs.
10875
입력을 받으며 vector에 head의 위치를 계속 push_back한다. head[i] -> head[i] = 선분. 한번에 90도밖에 진로변경이 불가능하므로 이전 3개의 선분은 무시해도 된다. 교점을 구하는 깔끔한 식이 생각나지 않아 디버깅이 매우 짜증났다. 맨 마지막에도 방향이 남아있으므로 편하게 검사하기 위해 해당 방향으로 맵끝까지 head값을 추가해 주면 편하다. 결과값인 초는 길이와 같다.
1799
n*n 판이 아닌 (2n-1)*(2n-1)의 대각선으로 생각하고 비숍을 위치한 곳은 bitmask로 표시한다. 체스판을 보면 검은칸에 인접한 칸은 모두 흰칸이고 흰칸에 인접한 칸은 모두 검은칸이다. 그리고 해당 칸의 대각선은 모두 해당 칸과 같은 색이다. 이 성질을 이용하면 한번에 모두 구하는게 아니라 검은칸에서 가능한 최대 비숍 개수를 구하고(이 배치는 흰칸에 비숍을 위치하는 행위에 아무 영향을 끼치지 못한다) 흰칸의 경우를 구해서 더하면 결과값이 나온다.
1600
dx[] = {-1,1,0,0}
dx2[] = {나이트 움직임}
위치와 나이트 움직임 잔여회수를 같이 bfs로 돌리면 된다.
3190
10875번 문제를 풀고 왔다면 이 문제를 잘못 이해할 확률이 높다. 3190번은 이전 스텝을 마치고 해당 입력만큼 움직이는 방식이 아니라 처음부터의 절대적인 시간을 주는 방식이므로 3 D 15 L이면 3초동안 dir[0]방향으로 움직이고 15-3 = 12초동안 dir[1]방향으로 움직이는 방식이다. 변수의 제한(맵 크기는 100이지만 시간은 10000까지 나온다)을 보고 눈치 챌 수 있다. 맵 크기도 작으므로 몸통을 queue<pair>로 유지하면서 맵의 몸 위치를 마킹하면 손쉽게 할 수 있다.
12196 12197
블록들의 모양을 모두 vector배열에 만든다. 다른사람들의 방식은 잘 모르겠지만 나는 맨 위에 4줄을 추가하고 거기에 블록을 복사한 후 아래까지 얼마나 내려갈 수 있나를 계산하는 방식을 사용했다. 시간은 널널한 편이므로 12196을 통과하고 배열범위만 신경 잘 쓰면 12197도 쉽게 통과할 수 있다.
12100
easy는 5회까지 하므로 가지치기를 별로 하지 않아도 통과가 가능하다. bitmask로 2비트씩 끊어 방향을 전부 만들어 조사하는 방법과 dfs를 사용하는 방법이 있다.
12094
최적화가 관건.