알고리즘/백준 (51) 썸네일형 리스트형 [백준] 1562 계단 수 [JAVA] 문제링크 : www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 첫 자리 숫자의 경우 1~9까지 오게, 아닐 경우에는 1. 현재숫자가 0이면 다음은 1, 9이면 8 2. 현재 숫자가 0이나 9가 아니면 위 아래 숫자로 다음 숫자를 정했다. 이런 경우를 중복 없이 모두 확인한다. 재귀 탐색 중, 현재 상태가 0~9까지 모두 등장한 계단수인지 판단하기 위해 그 상태를 비트마스크로 확인했다. (10개가 등장했거나 안했거나(0 or 1)로 가능하기 때문에 10자리 이진수로 표현 가능 => 2^10 크기 배열 선언) 어떤 숫자가 등장했는지와 더불어 (몇 번째 수인지, 이전에 무슨 수를 골랐는지.. [백준] 13398 연속합 2 [JAVA] 문제링크 : www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static int N,ans; public static int arr[]; public static int dp[][]; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedRea.. [백준] 11657 타임머신 [JAVA] 문제링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 최단거리 알고리즘은 보통 다익스트라나 플로이드워셜만 풀어왔다. 이 문제는 벨만포드 알고리즘으로 풀린다. 벨만포드 알고리즘은 음수 가중치가 있는 경우의 문제의 경우를 풀 수 있는 것으로 사이클의 존재 또한 알 수 있다. import java.io.*; import java.util.*; public class Main { public sta.. [백준] 2629 양팔저울 [JAVA] 문제링크 : www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 무게는 500g 이하이고 개수는 30개 이하이므로 추를 가지고 셀 수 있는 무개의 최대 g은 15000이다. 확인하려는 무게는 40000g 이하이므로 15000g 초과에 대해서는 N일 것이다. 구슬이 항상 왼쪽에 있다고 가정할 때 추를 올리는 방법은 왼쪽에 올리거나 오른쪽에 올리거나 올리지 않는 것이다. bottom-up 방식으로 풀었으며 어떤 무게 x가 가능할 때 i번째 추를 가지고 무게를 잴.. [백준] 1948 임계경로 문제링크 : www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 출발점 s에서 e까지의 경로 중 가장 긴 길로 이동한 거리와 그 경로의 개수를 출력하는 문제이다. 간선의 방향이 존재하는 그래프이다. 위상 정렬로 출발점 s에서 어떤 x까지의 최장거리를 갱신했다. 어려운 점은 그 경로의 수를 구하는 것인데, 도착점에서 시작해서 시작점까지 가는 경로를 탐색했다. 이 때, x-> y로의 경로를 이용해서 도착점까지 갔는지를 파악하기 위해 dis.. [백준] 13424 비밀 모임 [JAVA] 문제링크 : www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 플로이드 워셜로 모든 거리정보를 구한 후 모든 거점에 대해서 비용을 모두 구해보고 가장 작은 거리인 거점을 출력한다 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new I.. [백준] 1248 맞춰봐 문제링크 : www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static int N; public static int ans[]; public static boolean visited [][]; public static String query; public static int len; public static char str[][]; publ.. [백준] 2023 신기한 소수 문제링크 : www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 처음에 문제를 보자마자 소수를 미리 구해두는 편이 편하다고 생각했지만 8자리까지 구하려고 하니 에라토스테네스의체로도 불가능할 것으로 생각했다. 메모리 제한은 4MB인 문제였다. 그래서 N자리인 수의 가장 큰 자리수부터 부분자리가 소수인 수들을 찾아갈 생각을 했다. 1부터 9까지의 수들을 넣어보고 소수이면 다음자리에 들어갈 수 있는 수를 다시 넣는 방식을 N자리의 수가 될 때까지 탐색했다... 이전 1 2 3 4 5 ··· 7 다음