목록백준 (475)

1일1알

백준 15683번 감시 C++

은근히 고려해야 할게 많은 쉽지는 않은 구현 문제이다. 각각의 cctv마다 감시할 수 있는 경우의 수가 다르다. 예를 들면, 1번 cctv는 상, 하, 좌, 우 4가지 경우를 감시할 수 있고, 2번 cctv는 상하, 좌우 2가지 경우를 감시할 수 있다. 이 경우들을 비트로 만들어서 저장하였다. 위, 오른쪽, 아래, 왼쪽 순서로 저장했고 감시할 수 있으면 1, 못하면 0으로 저장했다. 2번 cctv의 경우는 상하, 좌우 2가지 경우가 있기 때문에 1010, 0101 두 개를 저장했다. 다음은 백트래킹을 이용하여 모든 경우를 탐색했는데, 중간에 마스크를 이용해서 감시할 수 있는 지역을 알아냈다. 마스크는 1000부터 시작하여 오른쪽으로 한 칸씩 옮겨가는데, 각 경우마다 cctv와 &연산을 해서 0이 아니라면..
알고리즘 2022. 1. 7. 12:55
백준 14891번 톱니바퀴 C++

톱니바퀴의 각 정보를 벡터로 저장하고, 왼쪽으로 회전한다면 첫번째 원소를 erase하고 맨 뒤에 다시 넣고, 오른쪽으로 회전한다면 마지막 원소를 pop하고 insert하는 방식으로 작동하는 Rotate 함수를 만들었다. 그리고 Solve 함수에서 맞닿아있는 극이 다르다면 재귀적으로 함수를 실행하도록 하였다. rotDir을 회전 방향, dir을 진행 방향으로 설정하여 왼쪽으로 진행하는 것과 오른쪽으로 진행하는 것을 따로 시뮬레이션 하였다. 그리고 한쪽으로 진행했다면 처음 돌린 톱니바퀴는 돌아가있는 상태이기 때문에 반대쪽으로 한번 회전시킨 뒤 다른쪽으로 진행하였다. #include #include #include #include #include #include #include #include #include..
알고리즘 2022. 1. 6. 12:29
백준 16234번 인구 이동 C++

bfs를 이용하여 문제를 해결하였다. #include #include #include #include #include #include #include #include using namespace std; int n, l, r; vector v(50, vector(50)); int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> l >> r; for (int i = 0; i > v[i][j]; } } int cnt = 0..
알고리즘 2022. 1. 3. 22:07
백준 2225번 합분해 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. dp테이블을 dp[n][k]라고 하고, k개의 수로 n을 만들 수 있는 경우의 수 라고 하였다. 의외로 간단하게 해결할 수 있다. 예를 들어 dp[3][4]는 4개의 수로 3을 만들 수 있는 경우의 수인데, 마지막에 0이 온다면 3개의 수로 3를 만드는 경우의 수, 마지막에 1이 온다면 3개의 수로 2을 만드는 경우의 수, 마지막에 2가 온다면 3개의 수로 1를 만드는 경우의 수, 마지막에 3이 온다면 3개의 수로 0을 만드는 경우의 수 이다. 이 경우들을 모두 합하면 되기 때문에 점화식은 dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + dp[n-2][k-1] + .... dp[0][k-1] 이다. 그리고 테이블을 채워가다 보면 dp..
알고리즘 2022. 1. 2. 12:24
백준 3190번 뱀 C++

뱀이 이동할 때마다 위치를 큐에 넣고, 보드의 정보를 갱신해준다. 만약 이동한 위치에 사과가 없다면 몸의 크기는 그대로 유지해야 하기 때문에 pop을 해주고 pop한 위치를 아무것도 없는 칸으로 바꿔준다. 사과가 있다면 몸의 크기가 늘어나기 때문에 pop을 하지 않고 진행하면 된다. 그리고 회전 정보를 이용하여 뱀을 회전시키고, 다음 위치가 자신의 몸이거나 벽이면 반복문을 종료한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, k, l; vector bo..
알고리즘 2022. 1. 1. 12:58
백준 15686번 치킨 배달 C++

백트래킹을 이용하여 치킨집이 m개일 모든 경우를 구하고, 각 경우마다 각 집에서 가장 가까운 치킨집의 거리의 합 중 최솟값을 구하는 방식으로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; vector houses; vector wholeChickens; vector myChickens; int ans = 987654321; int GetDist() { int sum = 0; for (auto house : houses) { int ..
알고리즘 2021. 12. 31. 13:56
이전 Prev 1 ··· 71 72 73 74 75 76 77 ··· 80 Next 다음