문제 링크 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..
[BOJ] 백준 20936 - 우선순위 계산기 (SUAPC 2021 Winter)
문제 링크 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$를..
문제 링크 www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 기본적인 최소 스패닝 트리 문제입니다. 코스트가 $c$이상인 간선만 모아 최소 스패닝 트리를 만들어줍시다..
문제 링크 www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 풀이 초기 치킨 쿠폰이 $n$개, 그리고 도장을 $k$개 모으면 치킨 쿠폰이 하나 증가합니다. 1) 쿠폰 $n$개를 다 써서 만들 수 있는 새로운 쿠폰 수를 $c$라 합시다. $c = n / k$ (정수 나눗셈)입니다. 2) 갖고 있는 쿠폰을 $n*c$개만 썼다고 하고, 그렇게 만든 새로운 쿠폰을 $n$의 나머지에 더해줍니다. 3) 위 두 과정을 $n \geq k$인동안 계속 돌려줍니다. 4) 더 이..
문제 링크 www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 풀이 예전에 Persistent Segment Tree 연습한다고 풀었던 문젠데, 이번엔 Merge Sort Tree를 연습한다고 풀어보게 되었습니다. 머지 소트 트리는 트리의 각 노드마다 항상 아래 두 노드의 리스트를 정렬된 상태로 갖고 있도록 저장하는 세그먼트 트리입니다. PST는 개념상 2차원 세그먼트 트리인데, 공간 효율을 높인 세그먼트 트리라고 보시면 됩니다..
문제 링크 www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 3대의 기관차가 항상 같은 수의 객차를 끌게 됩니다. 결국 N개중 3개의 시작점을 골라 최댓값을 뽑는 문제라고 생각할 수 있습니다. 기관차가 끌 수 있는 객차의 수만큼 구간을 잡고, 그 합을 미리 계산해두면 편하게 구현할 수 있습니다. 정답 코드 #include using namespace std; int d[55'555][3]; int n, k, p[55'555], sum[55'555];..
문제 링크 www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 일반적인 DP이지만 방향을 잘 잡아주어야 합니다. 저 같은 경우 어느 방향에서 왔는지에 대한 정보를 함께 넘겨주어, 그 방향으로는 다시 전개를 안 하게끔 구현했습니다. (line 20) 정답 코드 #include #define INF 0x3f3f3f3f using namespace std; int n, m, p[1111][1111]; int dx[] = {0, 1, 0}, dy[] = ..
문제 링크 www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net 풀이 이름들을 순서대로 그룹 지어준다고 생각해봅시다. 각 그룹 값의 합의 상한은 노트의 폭과 같고, 그룹의 값은 (그룹에 포함된 이름의 길이 합 + [이름 개수] - 1)입니다. 간단한 DP로 풀 수 있습니다. $D[i]$: 그룹이 $i$번 이름으로 시작하고, 그 뒤의 모든 이름을 적절히 그룹으로 묶어주었을 때 남는 칸의 수의 제곱의 합의 최솟값 $[i], [i, i+..