https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 설명 N이 주어졌을 때 N보다 크거나 같고, 소수이면서 팰린드롬인 가장 작은 수를 출력하면 된다. 풀이 방법 이 문제는 소수 구하기와 팰린드롬 판별하기가 결합된 문제이다. 소수 구하기 에라토스테네스의 체로 구한다. 팰린드롬 판별 팰린드롬을 간단하게 판별하는 방법이 있다. 숫자를 문자열로 바꾼다. 문자열을 절반으로 나누어 각각 다른 변수에 저장한다. 뒤쪽 ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 설명 소수 구하기와 투 포인터가 결합된 문제였다. N이 주어지면 해당 N까지의 소수를 모두 구한 뒤 투 포인터를 활용해 합이 되는 연속된 합의 개수를 카운트하면 된다. 풀이 방법 소수를 구하는 방법으로는 에라토스테네스의 체를 활용한다. 이때 소수는 ArrayList에 담는다. 주의할 점은 대부분의 소수 탐색의 경우 N의 제곱근까지 수행하지만 이 문제의 경우 N까지의 소수들에 대한 연속합을 구하기 위해 ArrayList에 소수를 담아야 하므로 N까지 모든 수들을 탐색한다. for 문을 한 번 더 사용해서 첫 번째..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제 설명 가장 많이 입력된 책을 출력한다. 가장 많이 입력된 횟수가 같을 경우 사전 순으로 출력한다. 풀이 방법 HashMap을 활용해서 해결했다. 간단한 문제이므로 바로 코드를 보자. import java.io.*; import java.util.*; import java.util.stream.Collectors; class Main { public static void main(Str..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 설명 골드바흐의 추측은 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들어 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수 n이 주어졌을 때..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 설명 n개의 서로 다른 양의 정수로 이루어진 수열이 있다. 정수는 모두 1보다 크거나 같고 1_000_000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때 합이 x가 되는 두 수로 이루어진 쌍의 수를 구하는 프로그램을 작성해라. 풀이 방법 - 정렬, 투 포인터 기본적인 투 포인터 문제이다. 이 문제는 정렬과 투 포인터를 활용하면 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음 세 가지다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절이 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오. 풀이 방법 - DP DP 기본 문제로 유명한 문제이다. N = 6 이라고 가정해보자. 이 경우 호출되는 함수의 구조는 다음과 같을 것이다. f(3), f(2), f(1) 처럼 같은 연산이 계속 반복되는 것을 볼 수 있다...