기록방

👉 문제링크 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 🔸 문제 분석 🔸 학생번호를 중복되지 않도록 가장 짧게 만들 수 있는 길이를 출력한다. 번호를 줄일때는 왼쪽수 부터 버린다. 🔸 문제 풀이 🔸 학생 번호 문자열의 끝 부분에서 하나씩 길이를 늘려가며 중복되는 문자열이 있는지 확인해야한다. 끝 부분에 있으면 접근이 어려울 것 같아 문자열을 뒤집어서 저장 후 중복을 확인했다. 중복확인을 위해 문자열을 1부터 N-1까지 잘라가며 Set에 넣고 확인했다. 🔸 코드 🔸 import java.io.Bu..

👉 문제링크 1418번: K-세준수 첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 자연수의 소인수중 최대값이 K보다 크지 않으면 K-세준수이다. N이하의 자연수 중에 K-세준수의 개수를 구한다. 🔸 문제 풀이 🔸 1부터 N까지의 자연수들 각각 최대 소인수를 구하고, 그 값이 K를 넘는지 확인해야 한다. 소인수 인지 확인하기 위해 자연수를 N까지 키워간다. 현재 수가 소인수이면 그 수의 N보다 작은 배수들은 현재 수를 소인수 최대값으로 저장한다.(에라토스테네스의 체) 만약 현재 수가 이전에 배수로 소인수를 구했으면 그 수와 K를 비교하고, 이전에 구한 값이 없으면 현재 ..

👉 문제링크 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 🔸 문제 분석 🔸 N이 3x2^k (0

👉 문제링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🔸 문제 분석 🔸 N * M 행렬 맵에서 (1, 1)부터 (N, M) 까지 이동하는 최단거리를 구한다. 인접한 상하좌우로 1칸씩 이동할 수 있다. 이동할 수 있는 칸은 0, 벽은 1로 표시되는데, 1번 벽을 부수고 이동할 수 있다. 행렬에서 최단거리를 구하는 문제이므로 BFS를 사용한다. 벽을 부수고 먼저 도착했었던 칸을 벽을 부수지 않고 도착했다면, 이어서 탐색해보아야 한다. 벽을 부수지않고 먼저 도착했던 칸이면 더 탐색해..

👉 문제링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🔸 문제 분석 🔸 N * 3 보드판을 내려가며 최대,최소값을 구하는 문제이다. 내려갈 수 있는 방법이 3가지가 있는데, 브루트포스로 그래프 탐색하면 시간초과가 난다. 내려가는 방법이 아닌, 역으로 이전 줄을 보고 최대/최소값을 고르는 DP 방식으로 풀이할 수 있다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io...