문제 링크 11967번: 불켜기 풀이 BFS 문제 먼저 각 위치에서 스위치를 통해 켤 수 있는 위치는 인접 리스트와 같이 구현하였다. 방문한 자리를 표시하기 위한 visited와 불이 켜져있는 것을 표시하기 위한 room을 만들었다. 여느 BFS와 같이 queue를 이용해 구현한다. 현재 위치인 tx, ty에서 연결되어 있는 자리가 불이 꺼져있으면 불을 켜주면서 answer++해주고, 해당 위치가 방문했던 위치라면 queue에 push해준다. 상하좌우 진출하면서, 범위를 벗어나거나 방문했던 곳이라면 continue, 불만 꺼져있으면 visited 처리해준 뒤에, queue에 넣지는 않는다.(진출하지는 않음) 1번에서 불이 켜진다면 진출할 것이다. answer를 return한 뒤 출력한다. 코드 #incl..
문제 링크 9657번: 돌 게임 3 풀이 DP 문제 일단 돌을 1개, 3개, 4개 주을 수 있으니 dp[1] ~ dp[4]까지는 초기화해준다. dp에는 게임이 몇 번만에 끝나는지가 들어있다. 1개면 상근이가 1개를 줍고 끝나서 1, 2개면 상근이가 1개, 창영이가 1개 주워서 두 번만에 끝나니 2인 식이다. n까지 dp를 구하는데, 상근이가 1개를 주웠을 때 dp[i-1], 그니까 i-1개 남았을 때에서 상근이가 한 번 주운 1을 더해서 홀수가 되면 상근이가 이기는 거고, 아니면 창영이가 이기는 것이다. 첫빠따는 상근이기 때문에 dp[i-1], dp[i-3], dp[i-4]를 다 확인해보면서 홀수가 하나라도 나오면 상근이가 이길 것이다. 코드 #include using namespace std; int ..
문제 링크 전화번호 목록 풀이 해시 문제라고 했는데 정렬로 풀었다. a 번호가 b 번호의 접두어라고 한다면, 정렬을 했을 때 반드시 a 번호가 b 번호 앞에 나오게 된다. 임시 string인 tmp에는 접두어라고 가정할 번호를 넣는다. tmp가 비어있으면 tmp를 해당 번호로 갱신. 해당 번호에서 접두어를 뽑았는데 tmp와 같지 않아도 갱신. 같으면 해당 번호는 tmp를 접두어로 가진다는 것을 의미하므로 answer를 false로 한다. 코드 #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); s..
문제 링크 11000번: 강의실 배정 풀이 이런 겹치는 구간 문제는 구간의 시작을 1, 끝을 -1로 잡은 다음에 정렬해서 푸는게 베스트인 것 같다. 왜 1과 -1이냐면 겹치는 구간의 개수를 잡기가 편함 강의 시간의 구간을 입력받으면서 v에 구간의 시작은 1, 끝을 -1로 해서 pair로 집어넣는다. v를 정렬하면, 구간의 시간 순으로 정렬될 것이다. 하나씩 살펴보며, 겹치는 구간의 개수인 cnt에 v[i].second를 구해주면 현재 시간에서 겹치는 강의의 개수가 나오게 될 것이다. 예제를 예로 2번까지 마치면 (1,1), (2,1), (3,-1), (3,1), (4,-1), (5,-1)가 될 것이다. 앞선 시간에서 강의를 시작했는데 (second가 1인데), 바로 뒤에서도 강의를 또 시작하면 (seco..
문제 링크 1644번: 소수의 연속합 풀이 투포인터랑 누적합 문제. 투포인터는 항상 헷갈리는게 각 포인터를 양 옆에 설정하느냐 아니냐 생각이 드는데 .. 그냥 같은 방향에서 시작하는 게 맞는 것 같다. 에라토스테네스의 체를 이용해서 n까지의 소수들을 구해준다. 여기서 팁은 i가 굳이 n까지 갈 필요 없이 제곱근까지만 구해주면 된다는 것 소수들의 누적합을 구해 sosuSum에 넣어준다. 투포인터를 이용해 연속합이 n인 구간의 경우의 수를 구해주는데, 여기서 투포인터를 사용한다. 각 포인터는 0과 1 인덱스로 설정한 뒤, en에서 st를 빼주면 구간의 합이 나온다. 이 합이 n과 같을 경우는 answer++ 2번과 상관없이 포인터를 재설정해줘야 하는데, n보다 큰 쪽에 넣든 작은 쪽에 넣든 상관없이 같을 때..
문제 링크 1368번: 물대기 풀이 최소 신장 트리인데 그래프 변형이 필요한 문제 어찌됐든 하나의 논에는 우물을 파야하기 때문에 노드를 하나 추가해서 (나같은 경우는 0번 노드) 각 우물을 파는 경우까지 최소 신장 트리로 구한다. 나머지는 크루스칼 알고리즘으로 union-find를 사용하면 여느 최소 신장 트리 문제와 비슷하다. 코드 #include #include #include #include #include using namespace std; int find(int node, vector& parent) { if (node == parent[node]) { return node; } else { return parent[node] = find(parent[node], parent); } } voi..
문제 링크 2531번: 회전 초밥 풀이 투 포인터 문제 보통 이런 종류 문제는 set을 먼저 생각하게 되는데, 이렇게 크지 않은 숫자로 있다면 그냥 배열로(index) 체크하는 게 나을 듯 함 0번째 인덱스부터 k개의 스시 종류를 체크해둔다. 초밥은 1번부터 d번까지 있기 때문에, 각 인덱스에 해당 인덱스 스시가 몇 개 들어가있는지 있게 된다. check 함수는 그 스시 배열에서 쿠폰을 사용할 무료 스시는 빼고 가짓수를 체크하게 된다. 이제 1번째 스시부터 하나씩 k개를 체크해보는데, 1번에서 구했던 종류에서 앞에 하나 빼고 뒤에 하나 추가하는 식으로 sushi 배열을 갱신하고 check한다. 이 때 인덱스를 넘어갈 경우, 해당 벨트는 원형 배열? 이기 때문에 인덱스 계산을 통해 앞의 인덱스를 구해준다...
문제 링크 18809번: Gaaaaaaaaaarden 풀이 백트래킹이라는데 BFS에 조합 문제인 것 같다. 입력을 받으면서 배양액을 뿌릴 수 있는 땅을 구해놓는다. 1번에서 구한 땅에 이제 배양액을 뿌릴 차례인데, 순열로 처리한다. 종류에 따라 상수로 정의했고 (EMPTY, GREEN, RED, FLOWER) 만약 뿌릴 수 있는 땅이 7개인데 초록색 배양액이 3개, 빨간색 배양액이 2개라면, water 배열은 {0,0,1,1,1,2,2}가 될 것이고 이를 순열처리해서 구하면 모든 조합대로 배양액을 뿌릴 수 있게 된다. BFS는 여느 BFS와 같이 queue를 이용해서 풀면 된다. 코드 #include #include #include #include #include #define INF 2501 using..
문제 링크 15663번: N과 M (9) 풀이 순열 문제인데 백트래킹 대신 next_permutation 함수 연습할 겸 풀었다. 여느 순열 문제와 같이 풀면 되지만, 중복을 제거하기 위해 마지막으로 구한 순열과 현재 구한 순열이 같지 않으면 출력하도록 했다. 코드 #include #include #include using namespace std; int arr[9]; int n, m; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i > arr[i]; } sort(arr, arr + n); vector pre; do { vector cur; for (int i = 0; i ..
문제 링크 1600번: 말이 되고픈 원숭이 풀이 BFS로 푸는 문제. 처음에 메모리 초과가 났는데, 말로 오는 경우와 그냥 오는 경우 방문 처리를 같게 해서 그랬음 먼저 원숭이가 갈 수 있는 위치를 정해주기 위한 dy와 dx를 지정한다. 입력을 받으며 dist도 INF로 초기화해준다. dist 배열은 3차원 배열인데, 말로 이동한 횟수의 각 위치 거리를 계산하기 위함이다. BFS를 통해 탐색한다. q는 tuple로 각 위치와 말로 이동한 횟수를 넣어준다. 원숭이가 이동할 수 있는 자리는 12개인데, 말로 이동한 횟수가 k를 넘어서면 말로 이동을 못하기 때문에 continue 해당 위치가 범위를 넘어서거나, 갈 수 없는 위치라면 continue 말로 오는 경우 dist[ny][nx][cnt+1]이 왔던 위..
