문제 링크 www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 오일러 파이함수 $\phi(n)$를 구현하는 문제입니다. 어떤 수 $n$의 소인수 개수를 $m$개라 합시다. $$\begin{eqnarray}\phi(n) &=& n\prod_{p|n}(1-\dfrac{1}{p}) \\ &=& n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_{m}})\end{eqnarray}$$ 식의 앞에서부터 차례대로 전개하는 방식으로 구현하시면 됩니다. 정답 코드 #inc..
문제 링크 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 1) 아직 방문한 적 없는 칸에서 dfs를 돌려 갈 수 있는 곳까지 간 후, 인구수의 평균을 구해줍시다. 2) 그 칸에서 다시 한번 dfs를 돌려 각 나라의 인구수를 1에서 구한 평균값으로 바꿔줍니다. 3) 더이상 인구수의 변화가 없을 때까지 반복해주면 됩니다. 정답 코드 #include #define TEST int _tt; cin >> _tt; while(_tt--) #defi..
문제 링크 www.acmicpc.net/problem/20936 20936번: 우선순위 계산기 국렬이는 두 번씩이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 이대로라면 죽을 때까지 계산기를 우려먹을 생각이고, 당신은 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계 www.acmicpc.net 풀이 우선순위 큐를 이용한 구현 문제입니다. 사실 복잡한 구현 문제라 이해하기 쉽게 쓰기 힘들어 보여 귀찮아서 안 쓰려했는데.. 그래도 써야죠... 역시 알고리즘 문제는 푸는 것보다 설명하는 게 더 힘듭니다.. 전체적인 풀이 1) $X_1\ Op_1\ X_2\ Op_2\ X_3\ Op_3\ ...\ Op_{n-1}\ X_n$ 꼴의 수식이 공백 없이 주어집니다. 이를 적절히 처리하여 $X$와 $Op$를..