본문 바로가기

분류 전체보기

 (265)
백준14430 - 자원 캐기 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주 www.acmicpc.net 이차원 배열에서 갈 수 있는 방향이 아래와 오른쪽만 주어져서 다이나믹 프로그래밍을 이용하여 풀었다. 현재 칸으로 갈 수 있는 최대의..
백준11659 - 구간 합 구하기4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀었다. 구간의 합을 구하기 위해서 숫자의 처음부터 각 숫자의 위치까지의 모든 숫자의 합을 구하여 저장한다. 그런 다음 끝 구간까지의 합에서 구간이 처음 시작하는 직전까지의 모든 숫자 합을 뺀다. 그것을 출력하면 답이다. #include #define MAX 10000..
백준11559 - Puyo Puyo https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net BFS를 이용하여 해결한 문제이다. 블록이 상하좌우로 4개가 연결되면 블록이 사라진다. 또한 동시 다발로 사라지는 블록은 1회로 세야 한다. 이점만 주의한다면 해결할 수 있다. 그리고 블록은 밑으로만 내려온다고 문제에서 주어졌기 때문에 2차원 배열을 탐색할 시에 아래부터 탐색하여 위로 올라가는 방법을 써야지 빈 공간을 매꿀 수 있다. #include #include #include #include #define WIDTH 7 #define HEIGHT 13 using namespac..
백준1325 - 효율적인 해킹 https://www.acmicpc.net/problem/1325 1325번: 효율적인 해킹 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다. www.acmicpc.net 간단한 bfs 문제였다. 입력시에 b가 출발점이고 a가 도착점이라는 사실만 잊지 않으면 쉽게 푼다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define MAX 10001 using namespace ..
백준1780 - 종이의 갯수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 분할 정복 문제다. 각 종이의 모든 칸을 탐색한 다음 하나의 숫자만으로 이루어져 있는지 확인하고 그렇지 않다면 종이를 가로와 세로로 ..
백준14938 - 서강그라운드 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 www.acmicpc.net 플로이드 와샬을 이용하여 풀었다. n개의 마을이 주어지고 서로 도달할 수 있는 비용이 주어져 있는 상태이기 때문에 플로이드 와샬을 ..
백준15723 - n단 논법 https://www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net 플로이드 와샬로 접근하여 푼 문제이다. fr과 to사이를 그래프로 정의하여 특정 정점을 거쳐서 to에 도달할 수 있다면 T를 출력하고 그렇지 않으면 F를 출력하였다. #include #include #include #include using namespace std; int m, n; int d[26][26]; string s; char fr, to; //플로이드 와샬로 정의, k번째 정점을 거쳐 가면 가고자 하는 ..
백준16401 - 과자 나눠주기 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다. www.acmicpc.net 이분 탐색 문제이다. 시간복잡도 nlog(n)을 구현하면 되는 간단한 문제이다. 처음 시작을 1로 놓는 것을 까먹지 말자. #include #include #include using namespace std; int main() { int M, N; //M명의 조카, N개의 과..

티스토리툴바