나그네

1010번: 다리 놓기 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 사이트 개수 N, 동쪽의 사이트 개수 M을 입력받고 두 사이트를 잇는 경우의 수를 구하는 문제다. 조합을 사용하면 쉽게 풀 수 있다. nCr(조합): n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수 (단, 중복은 불가능) nCr = nPr / r! n*(n-1)*(n-2)*...*(n-r+1) 즉, nCr = ──────────── 이다. r*(r..

17087번: 숨바꼭질 6 문제 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 풀이 수빈이는 좌우로 D칸씩 이동할 수 있고 모든 동생을 찾기 위한 D의 최댓값을 찾는 문제다. 즉, 모든 수빈이와 동생 사이의 거리의 최대공약수를 구하는 문제다. 먼저 첫 번째 동생과의 거리를 D라 하자. 다음 동생의 위치를 입력받을 때마다 입력받은 동생과의 거리와 D의 최대공약수를 D에 저장한다. 따라서 D를 출력하면 정답이다. ..

1009번: 분산처리 문제 https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 풀이 컴퓨터가 10대이므로, a^b의 일의 자리 수를 출력하면 된다. 따라서 1에 a를 b번 곱해가며 일의 자리 수만 남긴다. 일의 자리 수가 0이 아니라면, 그 수를 출력하고 일의 자리 수가 0이면 10을 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); in..

1008번: A/B 문제 https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 정수를 입력받은 후 나눈 결과를 출력하면 되는 문제다. 절대오차가 10^-9 이하여야 한다는 조건이 있으므로 정수가 아닌 실수값으로 입력받고 여유롭게 소수점 이하 15번째 자리까지 출력한다. 코드 #include using namespace std; int main() { double a, b; cin >> a >> b; cout

1003번: 피보나치 함수 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 규칙을 찾는 것이 중요한 문제다. N 0의 횟수 1의 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 여기서 0의 횟수와 1의 횟수를 각각 살펴보면 0의 횟수: 1, 0, 1, 1, 2, ... 1의 횟수: 0, 1, 1, 2, 3, ... 이므로 각각은 1, 0으로 시작하는 피보나치 수열과 0, 1로 시작하는 피보나치 수열이다. 따라서 각각에 대한 피보나치 수열을 구하는 문제다. 코드 #include using namespace std; int..

1001번: A-B 문제 https://www.acmicpc.net/problem/1001 1001번: A-B 두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 정수를 입력받은 후 차를 출력하는 사칙연산 문제다. 코드 #include using namespace std; int main() { int a, b; cin >> a >> b; cout

1000번: A+B 문제 https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 정수를 입력받은 후 합을 출력하는 간단한 사칙연산 문제다. 코드 #include using namespace std; int main() { int a, b; cin >> a >> b; cout

2557번: Hello World 문제 https://www.acmicpc.net/problem/2557 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 풀이 Hello World를 출력하는 문제다. 코드 #include using namespace std; int main() { cout