devbelly

문제 https://www.acmicpc.net/problem/3078 알고리즘 구현 풀이 위치가 K+1이상 벗어나지 않으면서 이름의 길이가 같은 쌍의 갯수를 찾는 문제입니다. $N$제한이 30만이므로 $O(N^2)$을 사용해서 순서쌍을 찾기는 어렵습니다. 스택과 비슷한 느낌으로 현재 자신과 같은 길이가 이전에 몇개 있었는지를 기록하여 $O(N)$에 풀도록 합시다. 단 이것을 기록한 배열은 유효한(서로 친구)값만을 유지하기 위해서 위치 차이가 K가 넘어가면 해당 정보를 지우는 업데이트를 하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) {..

문제 www.acmicpc.net/problem/17026 알고리즘 스택, 정렬 풀이 직각이등변삼각형으로 된 산의 꼭짓점이 주어집니다. 산의 색깔이 같을 때, 구분되는 산의 갯수를 구하는 문제입니다. 산 자체를 관찰하면 조금은 헷갈릴 수 있는 문제입니다. 산을 산의 시작 좌표와 산의 끝 좌표로 치환하여 문제를 풀어 나가야 합니다. 즉 산을 선분으로 치환하면 문제는 $N$개의 선분이 주어질 때, 완전히 겹치는 선분을 제외하고 세는 문제로 바뀌게 됩니다. 바뀌게 된 문제는 시작좌표를 오름차순으로 정렬하되, 시작좌표가 같다면 끝좌표는 내림차순으로 정렬하여 풀면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..

문제 www.acmicpc.net/problem/15685 알고리즘 implementation 풀이 드래곤 커브들이 주어졌을 때, 네 모서리가 모두 드래곤 커브인 1x1 사각형의 갯수를 구하는 문제입니다. 다음 세대가 시작할 때, 이전세대에서 사용했던 방향 + 1로 드래곤 커브를 진행합니다. 이때 이전세대의 마지막 부분부터 이전세대의 첫 부분 순으로 다음 세대의 처음부터 다음 세대의 마지막부분의 방향을 결정합니다. 이를 관찰하여 구현해 풀면 되는 문제입니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x, y, d, g; cin >> x >> ..