전체 글505

• 

  [BOJ] 1208 부분수열의 합 2 - JAVA 1. 문제 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 2. 풀이 N이 40까지라서 [.. 코딩테스트/BOJ 2023. 7. 23.

• 

  [BOJ] 15666 N과 M (12) - JAVA 1. 문제 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 2. 풀이 N과 M (9) 풀이와 비슷하다. ststic 변수 int[] arr 입력받은 전체 숫자들 int[] p.. 코딩테스트/BOJ 2023. 7. 22.

• 

  [BOJ] 14938 서강 그라운드 - JAVA 1. 문제 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자. 2. 풀이 입력 N,M,R, 아이템 개수를 입력받는다. 양방향이기 때문에 길을 입력받을때 두 가지 모두 저장해둔다. 같은 구간이 여러 번 입력될 수도 있는 경.. 코딩테스트/BOJ 2023. 7. 21.

• 

  [BOJ] 11403 경로 찾기 - JAVA 1. 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 2. 풀이 중간 노드가 될 지점을 가장 바깥 반복문으로 놓고, 시작지점, 끝지점을 i,j로 설정한다. 각 노드별 모든 거리를 살펴보면서 길이 이어져있는지(=경로가 있는지) 체크한다. import java.io.*; import java.util.*; public class BOJ_11403_경로찾기 { public sta.. 코딩테스트/BOJ 2023. 7. 20.

• 

  [BOJ] 11779 최소 비용 구하기 2 - JAVA 1. 문제 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 2. 풀이 Node 클래스 버스 노선을 저장하는 클래스다. 도착 도시,.. 코딩테스트/BOJ 2023. 7. 19.

• 

  [BOJ] 1504 특정한 최단 경로 - JAVA 1. 문제 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점.. 코딩테스트/BOJ 2023. 7. 18.

• 

  [BOJ] 13172 Σ - JAVA 1. 문제 13172번: Σ모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.www.acmicpc.netS1/N1 + S2/N2 + ... + SM/NM b의 모듈러 곱셈에 대한 역원 b-1은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다. b^-1 × b ≡ 1(mod X) 소수 모듈러에서만 성립하는 페르마의 소정리에 의해 b^(X - 1) ≡ 1 (mod X)가 성립하기에, b^(X - 2) ≡ b-1 (mod X) 역시 성립함을 알 수 있다. 이제 이 방식으로 M 개의 주사위가 있고, i번째 주사위가 Ni면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 Si일 때, 각 주사위에 대.. 코딩테스트/BOJ 2023. 7. 17.

• 

  [BOJ] 2448 별 찍기 11 - JAVA 1. 문제 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 2. 풀이 Main 1. [N][N*2]칸 boolean 배열을 만든다.(static 변수임) 2. 별 찍는 메서드를 부른다. 3. 만약 board[i][j] 가 true면 별, false면 공백을 sb에 더한다. 4. 출력한다. static boolean[][] board; public static void main(String[] args) throws IOException { int N = Integer.parseInt(new BufferedRea.. 코딩테스트/BOJ 2023. 7. 16.

• 

  [BOJ] 15501 부당한 퍼즐 - JAVA 1. 문제 15501번: 부당한 퍼즐 현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다. 플레이어는 1 ~ n 까지 숫자가 www.acmicpc.net 현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다. 1. 플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다. 2. 또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다. 3. 이때, 플레이어가 수열에 대해.. 코딩테스트/BOJ 2023. 7. 15.

• 

  [BOJ] 1238 파티 - JAVA 1. 문제 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.. 코딩테스트/BOJ 2023. 7. 14.

• 

  [BOJ] 1918 후위 표기식 - JAVA 1. 문제 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다. 이 문제에서 우리가 다룰 표기법은 후위 표.. 코딩테스트/BOJ 2023. 7. 13.

• 

  [BOJ] 15663 N과 M (9) - JAVA 1. 문제 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야.. 코딩테스트/BOJ 2023. 7. 12.