본문 바로가기

CS/Algorithm90

[SWEA][C++] 5656 벽돌 깨기 문제 SW Expert Academy 5656번 벽돌 깨기 풀이 1. 구슬을 쏠 index(w,가로값) 지정 2. 해당 index의 맨 위 벽돌부터 연속적으로 다 깬다. 3. 빈 공간 없이 메워준다. 4. n회가 끝나면 남은 벽돌 수를 체크한다. 1. 구슬을 쏠 index(w, 가로값) 지정 DFS로 모든 경우를 다 따져줍니다. 2. 해당 index의 맨 위 벽돌부터 연속적으로 모두 깬다. 이때, 백트레킹이 가능하도록 임시 map인 tmap을 복사해줍니다. 2-1. for문으로 tmap[i][index]>0 인 경우를 찾아 start값으로 정합니다. 2-2. tmap[i][index]==1 인 경우, 해당 칸만 0으로 바꾸어줍니다. 2-3. tmap[i][index] > 1 인 경우, 그 이상인 경우는 .. 2020. 4. 17.
[BOJ][C++] 17471 게리맨더링 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 두 팀으로 나누되, 갯수가 정해져있지 않은 조합 문제입니다. 코드가 다소 깔끔하지 못한 점 양해 부탁드립니다. 크게 세 단계로 나누어 풀이했습니다. 1. 두 팀으로 나누기 2. 나눠진 팀의 연결 상태 확인 3. 인구 차이 최소값인지 확인 1. 두 팀으로 나누기 (DFS) DFS로 팀을 나눕니다. team배열에 0과 1로 구분을 해줍니다. 이때, [0,0,0,1,1,1] 과 [1,1,1,0,0,0]은 같은 결.. 2020. 4. 16.
[BOJ][C++] 17135 캐슬 디펜스 문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 5단계로 나누어서 구현을 했습니다. 그리 효율적인 것 같진 않은데, 더 좋은 방법이 있다면 공유해주세요! 1. 궁수 자리 배치(DFS) 2. 궁수들의 공격할 적 정하기(적이 모두 사라질 때까지 반복) 3. 공격받은 적 없애기 4. 적의 이동 5. 결괏값 확인 1. 궁수 자리 배치 조합으로 구현했습니다. 2. 궁수들의 공격할 적 구하기 궁수 자리 배치가 끝나고 cnt==3 조건이 만족되면, 궁수 3.. 2020. 4. 14.
[SWEA][C++] 2112 보호필름 문제 SW Expert Academy 모의 문제 2112 보호필름 풀이 열마다 k개 연속으로 A 혹은 B 보호필름이 있으면 합격입니다. 모든 열이 이 조건에 만족하려면, 최소 몇 개의 행에 투약을 해야하는지가 문제입니다. 1. 투약 횟수를 지정해 줍니다. 2. 투약 횟수만큼 조합을 해줍니다. DFS를 이용했습니다. 3. 모든 열이 합격 기준에 만족하는지 확인합니다. 처음 구현했을 때 시간 초과가 나서 벡터를 배열로 바꾸고, 하나의 열이라도 합격 기준에 미치지 못하면 바로 빠져나오도록 최대한 가지치기했습니다. 시간 관리에 유의하면서 풀어야 하는 문제입니다. 코드 #include using namespace std; int answer = 987654321; int map[14][22]; int d, w, .. 2020. 2. 17.

티스토리툴바