https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 예전에 소수 판별 알고리즘으로 유명한 에라토스테네스의 체 관련 문제를 푼 적이 있는데 그거랑은 다른 문제이다. 그건 시간 초과나고 어려웠는데, 이 문제는 그냥 에라토스테네스의 체의 원리를 적용해서 풀어보는 문제이다. 숫자 N에 대해 에라토스테네스의 체를 적용하여 소수가 아닌 수를 지워나갈 때, K번째로 지워지는 수를 찾는 문제이다. 각 수의 지워졌는지 여부를 파악할 boolean 배열을 만들었다. 1. K번째로 지워지는 수를 찾을 때까지 반복한다. 1. 아직 지우지 않은 수 중 가장 ..

https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 예전에 풀었던 백준의 탑 문제(https://www.acmicpc.net/problem/2493)와 비슷하다고 생각했다. 각각의 높이가 다르고, 어느 한쪽에서 보았을 때 뒤에 있는 것들이 보이는지를 판단해야 한다. 탑 문제의 해설을 들었을 때, 스택을 사용해서 풀 수 있다고 해서 이 문제도 스택으로 접근해서 풀었다. 오른쪽에서 보았을 때, 제일 오른쪽에 있는 것보다 큰 것만 남아있어야 한다. 스택에 h..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 이것도 예전에 푼 적이 있는 문제이다. 문제를 딱 보면 재귀를 사용하는 분할정복 문제이다. 하지만 시간 제한이 0.5초로 시간에 유의해야 하는 문제이다. 역시 예전에 풀었을 때, 첫 시도에서 시간 초과가 났었다. 모든 사분면에 대해 재귀를 돌리다가 시간 초과가 났었다. 시간 초과가 나지 않기 위해서는 재귀를 돌리기 전에, 내가 탐색하고자 하는 좌표가 어디 사분면에 있는지 먼저 파악을 한 ..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 예전에 풀었던 문제이다. 하지만 풀이가 생각이 잘 나지 않았다.. DP로 풀어야 하나 생각했는데, 더 간단한 풀이가 있다. 1. 처음에 5로 나눠떨어지면 5로 나누고 정답을 도출하고 끝낸다. 2. 하지만 처음부터 5로 나눠떨어지는 수가 아니라면 5로 나눠떨어질때까지 3을 뺀다. 3. 계속 3씩 빼다가 0이하로 떨어지면 결국 불가능한 것이다. 코드 import java.util.Scanner; public c..

https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 브론즈 문제인데 어렵게 풀었다... 처음에는 규칙을 찾아보겠다고 각 행과 열을 수열로 생각해 공차를 찾아보기도 했지만, 수식으로 표현하기에 너무 복잡해 보여서 포기했다. 계속 규칙을 찾지 못하고 미루고 있다가 다른 사람의 규칙 힌트를 듣고 풀 수 있었다! 근데 이마저도 스터디원의 다른 풀이와 비교했을 때는 복잡하게 푼 편이다. 지그재그로 반복이 되는데, 그 반복되는 패턴 4가지를 이용하여 원하는 숫자가 나올 때까지 반복한다. → : 한 번만 움직인다. ↙ : 처음에는 1번, 그 다음에는 3번, 5번, .. 움직인다. ↓ : 한 ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 일년 전에 알고리즘 스터디할 때 풀어봤던 문제이다. 그때는 못 풀어서 해설을 참고해서 풀었는데, 이번에는 해설을 참고하지 않고 온전히 내 힘으로 풀었다. 실력이 는 거 같아서 뿌듯했다! 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 1. 배열의 정보를 입력받을 때, 치킨집의 좌표를 클래스로 생성된 객체의 리스트로 저장한다 2. 리스트에..