Problem Solving (25) 썸네일형 리스트형 [백준 17780 C++] 새로운 게임 새로운 게임 문제 링크 (BOJ 17780번 문제): https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 *실수하면 안되는 부분* 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다. 1. 바.. [백준 10021 C++] Watering the Fields Watering the Fields 문제 링크 (BOJ 10021번 문제): https://www.acmicpc.net/problem/10021 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 문제 설명 BOJ 10021번.. [백준 10986 C++] 나머지 합 백준 10986번 나머지 합 문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 풀이 백준 10986번 나머지 합 문제는 누적합을 이용한 문제로 [i, j] 구간 합이 M 으로 나누어 떨어지는 경우의 수를 세는 문제입니다. 해당 문제를 모든 구간 합을 구해서 M으로 나눌 경우, 시간 초과가 발생하게 됩니다. 그 이유는 N 값이 10^6 이기 때문에 O(N^2) 방법으로는 문제를 해결할.. [백준 1208 C++] 부분 수열의 합 2 백준 1208번 부분 수열의 합 2 문제 링크 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 백준 1208번 부분 수열의 합2문제는 백준 1182번 부분 수열의 합 방식대로 문제를 풀면 시간 초과가 난다. 그 이유는 정수의 개수가 20에서 40으로 늘어났을 뿐만 아니라 시간 2초에서 1초로 바뀌었기 때문이다. 그렇기에, 1208번 같은 경우에는 부분 수열의 합 계산을 나눠서 진행해주어야 한다... [백준 2638 C++] 치즈 치즈 문제 링크 (백준(BOJ) 2638번 문제): https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 백준 2638번 치즈 문제는 흔히 BFS (Breadth First Search) 알고리즘을 사용하는 문제이다. 이 문제에서 주목할 점은 치즈의 내부와 외부를 구분하는 것이 핵심이었다. 그리하여, 쓴이는 MAP을 돌면서 0인 부분에서 BFS를 시행하여 각각의 (치즈가 없는)공간을 번호로 나눠주었고 여러 공간들 중에 BFS .. [백준 2407 C++] 조합 조합 문제 링크 (백준(BOJ) 2407번 문제): https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 풀이 백준 2407번 조합 문제는 Combination 값을 구해서 출력하는 단순한 문제다. 파이썬을 사용한다면, 이 문제에 테스트 케이스로는 Integer Overflow가 발생하지 않아 쉽게 풀 수 있다. 하지만, C++을 사용한다면 Combination(100,50)의 경우 값이 10^29승 정도 되는 값이 나오게 되어 Integer Overflow가 발생한다. 그리하여, C++에서 이를 구현하기 위해선 __uint128_t 타입을 사용하면 위와 같은.. [백준 1167 C++] 트리의 지름 트리의 지름 문제 링크 (백준(BOJ) 1167번 문제): https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 설명 백준 1167번 트리의 지름 문제는 가중치가 있는 트리에서 노드 간에 거리가 가장 먼 트리의 지름을 구하는 문제이다. 문제 풀이 백준 1167번 트리의 지름 문제는 깊이 우선 탐색(Depth First Search) 혹은 너비 우선 탐색(Breadth First Search) 알고리즘을 사용하여 풀 수 있는 문제.. [백준 1504 C++] 특정한 최단 경로 오늘은 백준(BOJ) 1504번 파티 문제에 대해 다뤄보겠습니다. 파티 문제 링크 (백준(BOJ) 1504번 문제): https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 설명 백준 1504번 특정한 최단 경로 문제는 1번 정점에서 N번 정점까지 도달하는데 V1과 V2를 무조건 거쳐서 N번 정점에 도달해야하는 문제이다. 문제 풀이 백준 1504번 특정한 최단 경로 문제는 최단 경로를 구하는 문제이므로.. 이전 1 2 3 4 다음
