나그네

27960번: 사격 내기 문제 https://www.acmicpc.net/problem/27960 27960번: 사격 내기 A, B, C는 올해에도 예비군 훈련을 받으러 간다. 이번 예비군 훈련 과정 중에는 영점 사격이 있으며, 10개의 과녁 각각에 점수를 매겨 맞춘 과녁 점수의 총합을 측정한다. 과녁을 맞혔을 때, 과녁별 www.acmicpc.net 풀이 과녁의 점수가 2의 n승 꼴의 연속이므로 어느 과녁을 맞췄는지 점수만으로 알 수 있다. 따라서 점수를 2진법으로 변환한 다음 XOR 연산을 수행해 다시 10진수로 바꾸어 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int a, b; ..

27959번: 초코바 문제 https://www.acmicpc.net/problem/27959 27959번: 초코바 밤고는 $100$원 동전을 $N$개 갖고 있고, 그 돈으로 가격이 $M$원인 초코바를 사 먹으려고 한다. 밤고는 갖고 있는 돈으로 초코바를 사 먹을 수 있는지 알고 싶어 한다. 밤고가 가진 돈이 초코바의 www.acmicpc.net 풀이 100원 동전 N개로는 100 * N원 이하의 초코바만 살 수 있으므로 100 * N ≥ M인 경우 초코바를 살 수 있다. 이 경우 Yes를 출력하고 이외의 경우 No를 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin..

2041번: 숫자채우기 문제 https://www.acmicpc.net/problem/2041 2041번: 숫자채우기 N×M 크기의 격자에 적절히 수를 채우려 한다. 단, 인접한 수들의 차이로 1부터 (2NM-N-M)까지의 수가 한 번씩 나오도록 채우려 한다. N=2, M=2인 경우를 예로 들면 다음과 같은 방법이 있다. 위와 같 www.acmicpc.net 풀이 애드 혹 문제인 만큼 다양한 풀이가 있을 수 있다. 내 풀이는 가장 큰 차이부터 줄여나가면서 채우는 것이었다. 예시와 함께 보자. 3×3 크기의 배열이라고 하자. 그러면 1부터 12까지의 차이가 모두 존재해야 한다. 가장 먼저 1을 배치하고 큰 차이부터 채울 것이므로 13을 옆에 둔다. 그러면 배열은 아래와 같이 될 것이다. 1 13 ? ? ?..

18116번: 로봇 조립 문제 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 풀이 같은 로봇의 부품끼리 집합을 만들어 집합의 크기를 구할 수 있어야 하므로 유니온 파인드를 사용한 분리 집합으로 풀 수 있다. 부품이 1부터 10^6까지 표현되므로 배열의 크기를 10^6으로 고정시켜야 한다. 처음에 각 부품은 자기 자신 혼자의 집합이므로 크기가 1이다. 따라서 집합의 원소의 수를 나타내는 cnt 배열을 1로 초기화해준다. I 쿼리가 입력되었을 때는 ..

2505번: 두 번 뒤집기 문제 https://www.acmicpc.net/problem/2505 2505번: 두 번 뒤집기 첫줄에는 숫자판의 크기를 나타내는 정수 N (5 ≤ N ≤ 10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다. www.acmicpc.net 풀이 먼저 왼쪽에서 오른쪽으로 진행하며 i번째 칸의 수가 i가 아닌 경우 i의 위치를 찾아 두 위치를 정답 배열에 추가하고 두 위치 사이의 모든 값을 reverse 한다. 그러면 i번째 칸의 수는 i가 되었으므로 다음 수로 넘어가 위 과정을 반복한다. 만약 정답 배열의 크기가 2보다 큰 경우, 답이 될 수 없으므로 위에서 했던 과정을 오른쪽에서 왼쪽으로 진행한다. ..

16567번: 바이너리 왕국 문제 https://www.acmicpc.net/problem/16567 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net 풀이 이어져 있는 더러운 칸을 하나의 집합이라 했을 때 몇 개의 집합이 있는지 카운트 수를 유지해 주면 된다. 현재 상태를 입력받을 때 N+2 크기의 배열을 만들어 0번 index와 N+1번 인덱스는 0으로 두고 1~N번 인덱스에 수를 입력받는다. 왼쪽부터 차례로 입력을 받으므로 입력이 더러운 칸일 때, 왼쪽 칸이 깨끗한 칸인 경우..

27866번: 문자와 문자열 문제 https://www.acmicpc.net/problem/27866 27866번: 문자와 문자열 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 $S$가 주어진다. 단어의 길이는 최대 $1\,000$이다. 둘째 줄에 정수 $i$가 주어진다. ($1 \le i \le \left|S\right|$) www.acmicpc.net 풀이 문자열 S의 i번째 문자를 출력하는 문제다. 문자열 s와 정수 i를 입력받고 s[i-1]을 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; int i; cin >> s >> i; cout

6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 두 집 사이의 거리만큼의 비용이 드는 가로등이 있고 가로등 불이 켜져 있는 도로로만 이동 가능하도록 유지하면서 최소 비용이 들도록 불을 꺼야 하므로 전체 간선의 가중치에서 최소 스패닝 트리(MST)의 가중치를 빼주면 된다. 코드 #include using namespace std; vector p; int find(int x) { if (p[x] != x) p[x] = find..

27939번: 가지 교배 문제 https://www.acmicpc.net/problem/27939 27939번: 가지 교배 키위별의 유전학에 따르면 가지의 교배는 두 가지 서로 다른 방식이 가능하다. 교배란 서로 다른 두 품종으로부터 이전에 존재한 적 없는 하나의 품종을 만들어내는 것이다. P-우선 교배: 흰색과 www.acmicpc.net 풀이 조수들은 P-우선 교배를 하기 때문에 보라색인 가지가 1개라도 섞여있다면 보라색 가지가 배출되고, 키위는 W-우선 교배를 하기 때문에 흰색인 가지가 하나라도 있다면 흰색 가지가 배출된다. 따라서 각 번호의 가지가 P인지 W인지 저장하는 배열을 만들어두고 각 조수가 가진 품종 중에 P가 몇 개인지 센다. P-우선 교배에 따라 P가 0인 경우 W를 1 증가시키고 모..

27880번: Gahui and Soongsil University station 문제 https://www.acmicpc.net/problem/27880 27880번: Gahui and Soongsil University station Soongsil University Station is famous as the deepest station on Seoul Subway Line 7. This station is so deep that the platform is on the B6. Gahui was surprised that she did not reach the platform after more than five minutes from the exit. Gahui wants to www.acmic..