https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 설명 소수 A를 소수 B로 바꾸는 최소 단계를 구해야 한다. A를 B로 바꿀 때는 한 자릿수만 바꿀 수 있으며 바꾼 수 또한 소수여야 한다. 또한 네 자리 소수만 허용하므로 0039와 같은 수는 안 된다. 풀이 방법 이 문제는 소수 구하기와 BFS가 결합된 문제이다. 소수 구하기 에라토스테네스의 체를 활용해서 해결한다. import java.io.*; import java.util.*; class M..

https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 설명 입력된 G값은 현재 몸무게의 제곱에서 기억하고 있던 몸무게의 제곱을 뺀 값이다. 현재 몸무게로 가능한 모든 수를 출력해야 한다. 풀이 방법 투 포인터를 활용해 간단하고 효율적으로 해결할 수 있다. 모든 수를 출력하는 것 외에 다른 제한이 따로 없어서 당황할 수 있는데 규칙을 찾으면 반복의 종료 조건을 찾을 수 있다. 예제 입력으로 흐름을 따라가보자. 먼저 기억하고 있던 몸무게를 left, 현재 몸무게..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 설명 주어진 조건대로 동작하는 시뮬레이션 문제이다. 문제를 잘 읽고 알고리즘을 구현해야 한다. 특별히 부연설명할 게 없어서 설명은 사이트를 참고하면 좋겠다. 풀이 방법 주어진 조건대로 구현하면 되는 심플한 문제이다. 대신 조건이 많아서 꼼꼼히 예외처리를 해줘야 한다. 필자는 큐를 활용해서 해결했다. BFS를 약간 변형했다. 코드를 읽어내려가면..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 문제 설명 문제가 길기 때문에 천천히 꼼꼼히 읽어보면서 문제와 조건을 이해해야 한다. 예제 입력 1을 통해 알아보자. 초밥이 위처럼 주어진다고 한다. 이 중에 어떤 한 접시부터 연속으로 k개의 접시를 먹으면 할인을 해주는 이벤트를 한다고 한다. 그리고 이 이벤트에 참여하면 서비스 초밥을 하나 더 준다고 한다. 이 초밥이 트레이에 없으면 하나 만들어서 준..

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 문을 한 번 더 사용해서 첫 번째..