https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 주어진 입력이 처음에 어떤 수열인지 판단하는 문제입니다. 규칙은 간단합니다. x 부터 시작해 x가 3의 배수이면 3으로 나눌 수 있고, x가 어떤 수든 2를 곱할 수 있습니다. 3을 나누고 2를 곱하는 규칙 밖에 없으므로 배열에서 중복된 값이 나올 수는 없습니다. 왜냐하면 x 를 기준으로 y가 되었는데 x = y 라고 한다면 (x / 3^n) * 2^m = y 인 것이고, 이는 ..
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS를 이용해 퍼즐을 풀 수 있습니다. 0의 위치를 기준으로 BFS를 돌리면 됩니다. 하지만 메모리가 아주 작기 때문에 배열이 아닌 string을 활용해 map의 키로 활용하여 해당 string이 조회되었는지 확인합니다. 코드는 다음과 같습니다. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; /..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 그래프가 주어져 있을 때 최소 스패닝 트리 (MST) 를 만드는 문제입니다. 전체 간선을 오름차순으로 정렬 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리를 만들면 됩니다. 크루스칼 알고리즘을 이용해 MST를 만들면 모든 마을을 이을 수 있는 최소 경로를 찾을 수 있게 되고 이 때 마지막 가중치를 가지는 간선 (연결 가능한 간선 중 가중치 최대) 인 것을 빼면..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 정말 주어진대로 구현만 되는 문제였습니다. 좀 더 간단하게 풀 수 있을 거 같지만, 잠이 와서 그냥 하드코딩으로 했습니다..... 토네이도가 이동할 때 이동하는 방향에 따라 모래가 분리되는 비율이 달라지는 것만 주의하면 크게 어려울 것이 없습니다. 주어진 비율대로 모래를 구하고, 소수점은 그냥 버리면 됩니다. 날려간 모래는 해당 위치에 더해줍니다. 그리고 알파 위치..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 해당 문자열이 회문인지 아닌지, 그리고 한 글자를 뺐을 때 회문인지 판단하는 문제입니다. 단순히 한글자 씩 빼서 회문인지 검사하면, string의 최대 길이가 100,000 이하 이므로 최악의 경우 100,000 * 50,000 번의 검사를 해야합니다. (한 번에 2개 문자 검사 가정) 그러므로 투 포인터를 응용하여 해당 문자열이 회문인 경우 계속 진행하고, 서로 다른 문자가 나온 경우, check count를 1개 올려줍니다..