7576 토마토
2602 돌다리 건너기
2616 소형기관차
1309 동물원
1670 정상회담 2
1012 유기농 배추
2667 단지번호 붙이기
7562 나이트의 이동
7576
1마다 bfs 돌리고 배열에 0이 남아있으면 -1, 시작부터 모두 다 익어있으면 0, 아니면 max값. bfs하면서 최대값을 구하면 제대로된 max값이 구해지지 않는다.
2602
x,y,k로 dp를 돌린다. x=돌다리에서 몇번째 칸인가. y=무슨다리인가. k=몇번째 key를 써야하는가. 시작할 땐 0부터 다리를 훑어가면서 0번key를 탐색하고 찾으면 ans += dp(x+1,1-y,k+1).
2616
d[i][j] = i번 기관차로 j번부터 끌었을 때 최대 승객 수.
1309
dp[i][j] : i번째 칸의 상태가 j일 때 가능한 경우의 수
상태를 0,1,2로 나눈다. 0 = 양쪽 다 비었음. 1 = 왼쪽에 사자. 2 = 오른쪽에 사자.
0 다음 혹은 이전에 올 수 있는 경우 = 0,1,2
1 다음 혹은 이전에 올 수 있는 경우 = 0,2
2 다음 혹은 이전에 올 수 있는 경우 = 0,1
취향에 맞게 처음부터 혹은 끝에서부터 dp돌리면 끝.
1670
원형으로 둘러놓고 0번자리를 기준으로 누구와 악수하냐에 따라 달라진다. 악수를 테이블을 가로질러 하게 되면 양쪽으로 나뉘게 되고 양쪽 경우의 수를 곱하면 된다. 입력이 항상 짝수라고 명시되어 있다.
1012
덩어리가 몇개있나 세는 문제. 1을 모두 큐에 넣고 bfs를 돌리면서 check[nx][ny]를 바로바로 true로 갱신해 주고 queue에서 처음부터 check배열이 false인게 있으면 cnt+1 해주면 된다.
2667
유기농 배추와 동일한 문제
7562
dx[] = { -2,-1,1,2,2,1,-1,-2 };
dy[] = { 1,2,2,1,-1,-2,-2,-1 };
check배열 갱신하면서 bfs돌리면 간단하다.