문제 문제 바로가기> BOJ 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 정렬 후 두 포인터를 이용하여 "좋은" 수를 찾을 수 있다. * 서로 다른 두 수의 합은 해당 수를 사용해서 만들어지면 안된다! #include #include #define MAX 2001 using namespace std; int N; int num[MAX]; void input(){ cin >> N; for(int i=0; i> num[i]; } void solution(){ sort(num, num+N); // 정렬 int ans..

문제 문제 바로가기> BOJ 2887번: 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST를 만드는 문제이다. 다만, 메모리 초과 방지를 위해 정렬을 사용하여 O(N2)이 아닌, O(3N)개의 비용 후보만 가지도록 해야한다! #include #include #include #include #define MAX 100001 using namespace std; vector X, Y, Z; struct edge{ int a, b, dist; bool opera..

문제 문제 바로가기> BOJ 5430번: AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱에 들어갈 숫자의 길이가 1 이상일 수 있다. (0 T; while(T--){ string p; cin >> p; int size; cin >> size; string arr; cin >> arr; deque dq; string num = ""; for(int i=1; i

문제 문제 바로가기> BOJ 13549번: 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 순간이동을 하는데는 시간이 소요되지 않으므로, 해당 위치에 최단 거리로 도착할 수 있도록, 시간을 업데이트해 줄 필요가 있다! #include #include #define MAX 100001 using namespace std; int N, K; int visit_time[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.ti..

문제 문제 바로가기> BOJ 1697번: 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 기존의 방문한 지점을 제외하고, 이동할 수 있는 총 3가지 방법으로 이동하면서 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 찾아주면 된다! #include #include #define MAX 100001 using namespace std; int N, K; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.t..

문제 문제 바로가기> BOJ 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수 1. j == coin[i] 인 경우, 동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1 2. j > coin[i] 인 경우, 해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1) #include #define INF 9876543..

문제 문제 바로가기> BOJ 2293번: 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열로 풀면 메모리 초과가 발생하므로 1차원 배열로 풀어야 한다. i원 동전을 사용하여 j원을 만들 때 j-coin[i]의 누적합만 알면 되므로 1차원 배열로 풀 수 있다. #include #define MAX 101 #define MAX_K 10001 using namespace std; int n, k; int coin[MAX], dp[MAX_K]; void input(){ cin >> n >> k..

문제 문제 바로가기 > BOJ 10021번: Watering the Fields 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 모든 필드를 최소 비용으로 연결하기 위하여 MST(최소 신장 트리)를 만들어서 문제를 풀..

문제 문제 바로가기> BOJ 9465번: 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 다이나믹을 이용해서 푸는 문제였다. dp[i][j-1] + dp[1][j]가 dp[2][j] 보다 작은 경우 dp[1][j-2] + dp[2][j]를 해주는 것이 최대값이 된다. 이를 i가 1인 경우와 2인 경우로 나누어 각각의 위치에서 스티커의 점수를 더하여 얻을 수 있는 최대값을 구해주었다! #include #define MAX 100001 using namespace std; int N; in..

문제 문제 바로가기> BOJ 2178번: 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 이용하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구할 수 있다! #include #include #define MAX 101 #define INF 987654321 using namespace std; int N, M; int maze[MAX][MAX]; int dist[MAX][MAX]; int dy[] = {-1,1,0,0}; int dx[] = {0,0,-1,1}; void input(){ cin >>..

문제 문제 바로가기> BOJ 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS와 BFS를 구현할 수 있는지를 보는 간단한 문제이다. 주의해야할 점은 "정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하기 때문에 미리 연결되는 node를 정렬해 두어야한다는 것이다! #include #include #include #include #define MAX 1001 using namespace std; int N, M, V; bo..

문제 문제 바로가기> BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 BFS를 이용해 탐색을 진행하면서, USADO(가중치)가 k이상인지 검사 해주었다! 전체 경로에서의 최소값이 최종 USADO가 되므로, 가는 경로에서 가중치가 한번이라도 k이상이면 그 동영상은 추천 받을 수 없다. #include #include #include #define MAX 5001 #define INF 1000000001 u..

문제 문제 바로가기> BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 주어진 조건을 만족하면서 다음 계단에 도착하는 방법은 다음과 같이 총 2가지이다. 1. 두 계단 전에서 현재 계단으로 : dp[i-2]+arr[i] 2. 한 계단 전에서 현재 계단으로 : dp[i-3]+arr[i-1]+arr[i] 따라서 위 점화식을 토대로 max 값을 찾아내면 된다! #include #define MAX 301 using namespace std; int N; int arr[MAX], dp[MAX]..

문제 문제 바로가기> BOJ 12865번: 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 0-1 knapsack 문제로, 다이나믹 프로그래밍을 이용하여 해결할 수 있다. dp[i][j] : i개의 물건을 가지고, 최대 무게가 j 일 때 담을 수 있는 최대 가치 #include #define MAX 101 #define MAX_K 100001 using namespace std; int N, K; int weight[MAX], ..

문제 문제 바로가기> BOJ 1238번: 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 파티가 열리는 마을에서 돌아오는 데 걸리는 최소 시간은 다익스트라 알고리즘으로 구할 수 있다! 하지만, 돌아오는 것은?! 그래프를 만들 때, 역방향 값을 저장해 놓고, 한 번 더 다익스트라 알고리즘을 이용하면, 파티가 열리는 마을에 가는 데 걸리는 최소 시간도 구할 수 있다! #include #include #include #define MAX 1001 #define INF 987..