kimtetris 님의 블로그

문제https://www.acmicpc.net/problem/15684 풀이문제 조건에 사다리를 최대 3개만 설치 가능하다는 것을 보고 바로 백트래킹으로 구현했습니다. 백트래킹의 진행 조건으로 사용한 것은 3개를 초과하는가? 현재 저장된 정보보다 값이 적은가? 조건에 맞도록 구현이 되었는가? 총 3가지입니다. 3개를 초과하는 경우엔 의미가 사라지고, 이미 저장된 답보다 커지면 불필요한 계산, 조건에 맞지 않으면 성립 자체가 되지 않기에 탈출 조건으로 지정해 줬습니다. void dfs(int n, int h, int cnt, int y){ if (cnt >= ans) return; if (check(n, h)) { ans = cnt; return;..

문제https://www.acmicpc.net/problem/10986 풀이먼저 구간의 총합에 대한 나머지 개수를 저장합니다. 이때 나머지 개수로 저장하는 이유는 구간을 정하는 상황에서 같은 나머지를 갖는 구간끼리 선택하면 M으로 딱 나눠 떨어지기 때문입니다. 예를 들어 1 3 2 5 2 8 2가 주어지고 3으로 나누는 상황이라는 가정하에 구간별 총합은 1 4 6 11 13 21 23이고 나머지는 1 1 0 2 1 0 2 입니다. 그러면 나머지 리스트에는 2 3 2가 저장됩니다. 이때 나머지를 저장하는 리스트의 크기는 int로 하면 차원이 축소되어 배열 크기 초과가 일어날 수 있기에 주의해줘야 합니다. long long mod[1001];...for (int i = 0; i > tmp; sum..

문제https://www.acmicpc.net/problem/15683 풀이문제를 접하자마자 cctv의 개수가 8개 이하라는 것을 보고 백트래킹을 통해 해결해야겠다는 아이디어를 생각했습니다. 다음으로는 x, y 이동 뱡향을 시계 방향으로 잡아주고, cctv번호에 맞는 감시 방향을 vector를 통해 미리 선언해 줬습니다. int room[8][8];int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};vector dir[6] = {{}, {0}, {0, 2}, {0, 3}, {0, 2, 3}, {0, 1, 2, 3}}; 다음 단계로 앞서 생각해 뒀던 백트래킹을 사용하여 단계를 진행했고, 해당 단계에서 cctv가 회전하는 것을 반영하기 위해 "(i + dir[n..