Tech/Problem Solving 썸네일형 리스트형 [백준 2206] 벽 부수고 이동하기 (Java) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 접근 방법 bfs를 이용해 풀어야하는 문제이지만 1번 벽을 부수고 이동이 가능하다는 특징이 있었다. 벽을 단 한번만 부술 수 .. [백준 2579] 계단 오르기 (Java) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 접근 방법 DP 방법으로 풀었으며, N번째 계단까지 올라올 때의 경우는 두가지가 있다. 첫 번째는 n-1 번째를 밟지 않고 온 경우 두 번째는 n-1 번째.. [백준 1463] 1로 만들기 (Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근 방식 다이나믹 프로그래밍으로 생각하여 풀이하였다. 소스 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] dp = new int[1000001]; dp[0] = 0; dp[1] = 0; for (int i = 2; i [백준 1003] 피보나치 함수 (Java) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근 방식 문제에서 C++ 코드를 제시한 것도 그렇고 정답 비율도 그렇고 전통적인 피보나치수열 구하는 코드로 풀기에는 의심스러운 것이 많은 문제였다. 시간 제한이 다른 문제들에 비해 많이 작은 것을 확인하고 다른 방식의 접근이 필요하다는 생각을 했다. f(n) = (f(n-1)의 f(0)개수와 f(1)개수의 합) * f(1) + (f(n-1)의 f(1)의 개수) * f(0) 이라는 점화식을 도출했다. 시간과 메모리 제한을 고려해서 주어지는 값이 40으로 크지 않기 때문에 바텀업 방식으로 미리 .. [백준 6588] 골드바흐의 추측 (Java) https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 접근 방식 에라토스테네스의 체 알고리즘을 이용해 소수를 먼저 구해 소수 리스트를 만든다. 입력 값 중 가장 큰 값을 기준으로 그 .. [백준 1644] 소수의 연속합 (Java) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 접근 방법 주어진 값 보다 작거나 같은 소수를 모두 구해 리스트에 담았다. 그 후 for문을 이용해서 소수 리스트의 0번째 값부터 차.. [백준 2485] 가로수 (Java) https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다. www.acmicpc.net 접근 방식 주어진 가로수의 간격 간의 최대공약수 == 최종 간격 최대 공약수는 유클리드 호제법을 사용하였다. 간격을 담은 배열을 만들어 주어진 가로수 간의 간격을 담고 앞에서부터 그 다음 값과 차례로 최대 공약수를 구해나갔다. 소스 코드 import java.util.Scanner; publ.. [백준 2580] 스도쿠 (Java) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 접근 방식 복잡해 보였지만 백트래킹이라는 큰 틀 안에서 해결 가능했다. 우선 스도쿠 판에서 0인 부분의 좌표를 List로 담았다. 첫번째 .. 이전 1 ··· 10 11 12 13 14 15 다음
