초보 개발자의 이야기, 릿허브

1. 문제이해 9656번: 돌 게임 2 (acmicpc.net) 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 탁자 위의 돌 N개가 있고, 상근이와 창영이는 게임을 하려한다. 두 사람은 번갈아가며 1개 또는 3개의 돌을 가져갈 수 있다. 마지막 돌을 가져간 사람이 질 때, 누가 이겼는지에 따라 출력을 달리하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 이전 돌 게임 문제와 풀이 방식은 동일하지만, 차이점은 마지막 돌을 가져간 사람이 진다는 점이다. 이전에 푼 돌 게임 문제에 대한 자세한 풀이와 코드는 아래 포스팅을 참고하자. https://beginnerdeveloper-lit.tistory.com/83 [C++] 백..

1. 문제이해 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 탁자 위의 돌 N개가 있고, 상근이와 창영이는 게임을 하려한다. 두 사람은 번갈아가며 1개 또는 3개의 돌을 가져갈 수 있다. 마지막 돌을 가져간 사람이 이길 때, 누가 이겼는지에 따라 출력을 달리하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 두 사람은 1개 또는 3개씩만 돌을 가져갈 수 있고, 마지막 돌을 가져간 사람이 이기게 된다. 그렇다면 과연 누가 마지막 돌을 가져가게 될지, 오늘도 예제를 통해 살펴보도록 하자. 돌의 개수 (N) 게임 과정 이긴 사람 1 1 상근(SK) 2 1 -> 1 창용(CY) 3 3 ..

1. 문제이해 7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net) 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 두 종류의 생명체 A, B가 있고, A는 B를 먹는다. 단, A는 자기보다 작은 B만 먹을 수 있다. 테스트 케이스의 개수(T)와, 각 테스트케이스에서의 A, B의 수와 크기가 주어질 때, A가 B를 먹을 수 있는 순서쌍의 개수를 구하는 것이 목표이다. 2. 문제풀이 A와 B의 수, 각각의 크기들이 주어질 때, A가 B를 먹을 수 있는..

1. 문제이해 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 주어진 숫자 N을 위와 같은 연산을 이용해 1로 만드려고 할 때, 최소 몇 번의 연산이 필요한지를 출력하는 것이 목표이다. 2. 문제풀이 주어진 정수 N을 최소 몇 번의 연산 뒤에 1로 만들 수 있는지를 구하는 문제이다. 문제의 예제 입력 1의 경우인 2는, "2. X가 2로 나누어떨어지면, 2로 나눈다" 에 의해 1번의 연산 후 1이 된다. 따라서, 최소 1번의 연산이 필요하게 된다. 예제 입력..

1. 문제이해 1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 첫째 줄에 도감에 수록된 포켓몬의 수 N과 맞춰야할 문제의 개수 M이 주어진다. 둘째줄부터, 번호가 1부터 N까지에 해당하는 포켓몬들을 차례로 입력한 후, 입력이 끝나면 M개의 문제를 입력한다. 이때, 번호가 입력되면 해당 번호에 해당하는 포켓몬의 이름을, 이름이 입력되면 해당 이름을 가진 포켓몬의 번호를 출력해야한다. 위와 같은 프로그램을 구현하는 것이..

1. 문제이해 9461번: 파도반 수열 (acmicpc.net) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그림과 같이 삼각형들이 나선형으로 놓인 도형이 주어진다. 첫 삼각형은 정삼각형이고, 변의 길이가 1이며, 다음과 같은 과정으로 정삼각형이 계속 추가된다. 파도반 수열 P[n]이 n번째 정삼각형의 한 변의 길이를 나타낼 때, 각 테스트 케이스의 P[n] 값을 출력하는 것이 목표이다. 2. 문제풀이 나선형으로 놓인 삼각형들이 다음과 같이 있을 때, n번째 삼각형의 한 변의 길이를 구하는 것이 목표이다. 삼각..

1. 문제이해 4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 입력받은 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 수 중 소수의 개수를 출력하는 것이 목표이다. (입력의 마지막에는 0이 주어진다.) 2. 문제풀이 주어진 n에 대해, n n; count = 0; if (n == 1) {// n이 1인 경우 count = 1; } else { for (int i = n + 1; i

1. 문제이해 3036번: 링 (acmicpc.net) 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 상근이는 N개의 링을 이용해 각각의 링들이 앞에 있는 링과 겹쳐지도록 놓았다. 상근이가 첫 번째 링을 한바퀴 돌릴 때, 나머지 링은 몇 바퀴 돌아가는지 기약분수 형태로 출력하는 것이 목표이다. 2. 문제풀이 첫 번째 링을 기준으로, 첫 번째 링이 한바퀴를 돌 때, 나머지 링들이 몇바퀴를 도는지를 기약분수 형태로 나타내야 한다. 링이 한바퀴를 도는데 걸리는 시간은 링의 반지름과 비례하므로, 이 점을 유의하고 예제를 보면 다음과 같다. 첫 번째..

1. 문제이해 1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 자연수 M과 N이 주어졌을 때, M과 N 사이의 소수를 모두 출력하는 것이 목표이다. 2. 문제풀이 자연수 M과 N 사이의 소수들을 오름차순으로 출력하는 것이 목표이다. 이전에 입력받은 자연수들 중 소수의 개수를 출력하는 문제를 푼 적이 있는데, 그와 유사한 방법으로 풀이했더니 시간초과가 발생했다. 풀이한 첫 번째 방법은 다음과 같다. for문을 통해, N부터 M까지의 수들을 2부터 자기자신 전까지 나누어보고, 그 중 나누어떨어지..

1. 문제이해 1748번: 수 이어 쓰기 1 (acmicpc.net) 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 1부터 N까지의 숫자를 이어서 쓰면 새로운 수를 얻을 수 있다. 이렇게 만들어진 새로운 숫자는 몇 자리 수인지 구하는 것이 목표이다. 2. 문제풀이 1부터 N까지의 숫자를 이어 썼을 때, 이어쓴 숫자가 몇 자리 수인지를 출력하는 것이 목표이다. 예를 들어, N이 8인 경우에는 12345678 이라는 8자리 수가 나타나며, N이 12인 경우에는 123456789101112 라는 15자리 숫자가 나타나게 된다. N의 값에 따라서 몇 자리 숫자가 나오게 되는지 아래 예제를 통해 확인하자. 1. N이 한 자리 자연수인 경..