본문 바로가기

분류 전체보기

 (265)
백준5549 - 행성 탐사 https://www.acmicpc.net/problem/5549 5549번: 행성 탐사 문제 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다. 상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 www.acmicpc.net 처음에 bfs로 풀었다가 시간초과나서 dp로 푼 문제이다. 문제에서 시작하는 점과 끝나는 점을 주었고 오른쪽과 아래로만 이동하면서 풀면 ..
백준1912 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1차원 DP를 사용하였다. 변수를 최댓값과 진행상황 두가지로 만들어 풀었다. 진행상황과 그 다음 숫자가 더했을 때 0보다 작으면 진행상황을 0으로 갱신하는 규칙과 진행상황을 0으로 하는 과정에서 현재 최댓값이 음수이면 그 다음 숫자와 크기 비교를 하여 더 큰 값을 최댓값으로 갱신해준다. 진행 상황을 더한 경우 0이상이면 현재 진행상황을 갱신하고 최댓값도 진행상황과 현재 최댓값을 비교하여 더 큰 값으로 갱신한..
백준10844 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2차원 DP를 이용하여 푼 문제다. DP의 규칙은 N자리 숫자의 수열의 갯수는 N - 1자리의 숫자들 중에서 끝자리가 1과 8인 경우의 수에 의하여 결정이 된다는 것이다. ex1.) 2자리 숫자가 21인 경우 3자리 숫자 210, 212 ex2.) 2자리 숫자가 32인 경우 3자리 숫자 321, 323 ex3.) 3자리 숫자가 878인 경우 4자리 숫자 8787, 8789 ex4.) 3자리 숫자가 210인 경우 4자리 숫자 2101 ex5.) 4자리 숫자가 8789인 경우 5자리 숫자 87898 예제를 보면 끝..
백준2565 - 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net LIS문제다. 벡터의 인자로 pair를 받은 뒤 A 가로등을 기준으로 오름차순 정렬을 한다. 정렬이 된 상태에서 B에 LIS를 실행하여 최대 증가 수열을 찾으면 된다. #include #include #include using namespace std; int main() { i..
백준11568 - 민균이의 계락 https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 정해진 순서대로 보여줄 것이다. 준민이는 앞의 카드부터 임의의 개수만큼 골라서 민균이에게 제시하게 되는데, 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 예를 들어 민균이가 보여준 카드가 {4, 9, 10, 9} 일 때 준민이가 {4, 9}를 골 www.acmicpc.net 항상 두려워하던 LIS문제를 풀었다. 시간복잡도 O(n) = NlogN을 활용하였다. 주목할 점은 현재 숫자가 이전 수열 결과의..
백준2210 - 숫자판 점프 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net BFS를 활용하여 푼 문제다. 행렬에서 방문한 곳도 재방문이 가능하도록 문제 조건을 주었다. 현재까지 탐색한 숫자의 갯수가 6개이면 6자리 숫자로 바꾸고 그 숫자를 탐색하였는지 체크하여 탐색을 하지 않았더라면 탐색을 하였다고 체크를 하고 카운팅을 +1 해주면 된다. #include #include #include #include using namespac..
백준2096 - 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에 2차원 배열을 이용한 DP로 접근했다가 메모리 초과 계속나서 1차원 배열을 이용한 DP로 해결한 문제다. 전에 있던 값을 다른 공간에 저장해놓았다가 규칙에 맞게 움직이면 된다. #include #include #include using namespace std; int n; int mat[3]; //현재 입력한 수 int res_big[3]; //최대만 찾아간 결과 int res_small[3]; //최..
백준1654 - 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분탐색을 활용한 문제다. 현재 만들 수 있는 랜선의 갯수가 주어진 랜선의 갯수 이상이면 답을 갱신한다. 답을 찾으면 범위를 반으로 줄여 큰 쪽으로 탐색하기 때문에 현재 길이와 비교 과정이 없어도 가장 최근의 찾은 길이가 답이 된다..

티스토리툴바