호지

dp와 비트마스크를 활용한 문제. 배열 dp[x][y][z]에서 x는 계단수의 길이, y는 0~9인 숫자, z는 비트마스크로 사용된 숫자를 체크한다. 길이가 1이면서 숫자 1~9가 사용되었을 때 dp를 채운다 (0으로 시작하는 수는 계단수가 아니므로 0은 제외) 길이가 2~n일때(len for문) 숫자 0~9에 대해(num for문) 비트마스크 0000000000~1111111111일 때(i for문) dp값을 채운다. i for문에서 해당 비트마스크를 순차탐색하여 dp를 채울 수 있는 이유는 길이가 1일때, dp[1][1][2], dp[1][2][4], dp[1][3][8]...이 1이고, 길이가 2일때, dp[2][0][3], dp[2][1][6], dp[2][2][1], dp[2][2][12].....

S, L, R로 채워진 grid가 주어졌을때, 사이클이 있는가 탐색하는 문제이다. grid의 최대값은 500이므로 char형 배열 board[500][500]을 선언하고, 각 방향에 대해 방문했는지 확인을 위해 int형 배열 moves[500][500]을 선언하였다. 각 위치에서 가능한 방향은 상하좌우 총 4가지이므로 비트마스크를 통해 방문확인을 한다. 위(0001), 오른쪽(0010), 아래(0100), 왼쪽(1000) 각 방향은 mx,my 배열에 저장되어있다. (↑→↓←) find함수는 이미 진행한 방향을 만나기전까지 경로를 계속 진행하며 탐색하고,(while문) 이미 진행한 방향을 만났을 때의 위치가 시작점이면서,(x==start_x, y==start_y) 처음 방향과 동일하다면(d==start_d..

long long 변수형을 써야되는데서 삽질을 했다.. 역시 변수의 최대범위는 잘 확인해야... 숫자들은 최대 길이가 50이상이므로 string 자료구조로 받아 처리해야 된다. ten_mod_k에 1%k, 10%k, .. 10^50%k값을 구한다 mod_k에 각 원소의 %k 값을 구하고, dp값을채운다 dp[a][b]에서 a는 비트마스크로 해당위치의 원소가 쓰였는지 확인하고, b는 0~k-1값으로, 비트마스크로 확인한 원소로 숫자를 만들었을때 나머지가 b인 개수이다. ex) n = 3, [1, 2, 3] k=2 d[1][0]=0, d[1][1] = 1, d[2][0] = 1, d[2][1] = 0, d[4][0] = 0, d[4][1] = 1 ten_mod_k와 mod_k, d배열을 통해 0 ~ (1>>..