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

1. 문제이해 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있을 때, 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 것이 목표이다. 2. 문제풀이 주어진 수열에서 합이 M이 되는 연속되는 경우의 수를 구하는 문제이다. 연속된 수들의 합만 취급하기에 그..

1. 문제이해 1359번: 복권 (acmicpc.net) 1359번: 복권 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 다음과 같은 룰의 복권이 있을 때, 지민이가 복권에 당첨될 확률을 구하는 것이 목표이다. “1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다!” 2. 문제풀이 지민이가 1부터 N까지의 수 중에 서로 다른 M개의 수를 골랐을 때, 복권과 적어도 K개의 수가 같으면 당첨이다. 조합, 확률 관련 문제로 고등학교 문제 푸는 것과 비슷한 느낌을 받았다.풀이 방법은 아래 그림과 같다. 문제의 예제 입력 4에 대한 풀이 예시이다.위 풀이방법을 일반화해보면 ..

1. 문제이해 https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 모든 자연수들에 대해 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수를 대표 자연수라고 한다. N개의 자연수가 주어질 때, 그 중 대표 자연수를 출력하는 것이 목표이다. (단, 대표 자연수가 2개 이상일 경우, 가장 작은 숫자를 대표 자연수로 출력한다.) 2. 문제풀이 문제의 의도만 잘 파악하면 어렵지 않은 문제이다. N개의 자연수 중 전체 차이의 합을 최소로 하는 값을 찾는 ..

1. 문제이해 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열의 원소의 개수(N)와 원소값이 주어진다. 이때, 배열의 배치 순서를 적절히 바꾸어 다음과 같은 연산을 수행했을 때 얻을 수 있는 최댓값을 구하는 것이 목표이다. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 2. 문제풀이 문제를 똑바로 읽자.. 차이를 최대로 라는 문제 제목과 점화식을 잘못 보고 한참 헤맸다. 문제의 점화식을 잘 봐야 한다..

1. 문제이해 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net A라는 사람이 B라는 사람보다 몸무게와 키가 더 클 때, A의 덩치가 B보다 크다라고 이야기 할 수 있다. 만약, 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다고 할 때, N명의 사람들의 몸무게와 키가 주어질 때, 각 사람들의 덩치 순위를 출력하는 것이 목표이다. 2. 문제풀이 N명의 몸무게와 키를 입력받아, 각 사람들의 덩치 등수를 출력..

1. 문제이해 https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 양의 정수 n에 대해서 d(n)은 n과 n의 각 자리수를 더하는 함수이다. 이때, n을 d(n)의 생성자라고 할 때, 생성자가 없는 숫자를 셀프 넘버라고 한다. 10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하는 것이 목표이다. 2. 문제풀이 10000 이하의 생성자가 없는 숫자, 셀프 넘버인 숫자들을..

1. 문제이해 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 영화감독 숌은 종말의 숫자가 들어간 영화제목을 지으려고 한다. 종말의 숫자란 '666'이 들어가는 숫자를 이야기하며, 666,1666,2666... 순서대로 커진다. 이러한 순서대로, 영화의 제목을 정할때, N번째 영화의 제목에 들어간 수를 출력하면 되는 알고리즘을 구현하는 것이 목표이다. 2. 문제풀이 문제를 처음 봤을 때 든 생각은 엥? 너무쉬운데? 라는 생각이었다. 하지만 이..