알고리즘 (30) 썸네일형 리스트형 [백준] 25208번 새벽의 탐정 게임 [C++] https://www.acmicpc.net/problem/25208 25208번: 새벽의 탐정 게임 새벽의 탐정 게임은 재미있는 2인용 보드게임이다. 한 명은 탐정, 다른 한 명은 도둑 역할을 맡는다. 게임은 $N$행 $M$열 격자 위에서 진행된다. 격자의 각 칸은 벽이 설치되어 있거나 비어있고, 역 www.acmicpc.net 문제 문제 요약 문제가 너무 김에 따라서 요약을 하자면, 위와 같은 판에 도둑, 탐정 두가지가 있는데, 탐정은 상하좌우 4가지 방향 중 한곳으로 움직일 수 있다. 탐정은 위의 전개도로 만들어지는 감옥을 본인 시작 지점에서 바닥이 뚫린 채로 시작하며, 움직이는 방향에 따라서 주사위처럼 비어있는 부분또한 움직이게 된다. 도둑을 가두기 위해서는 도둑이 있는 지점에 감옥의 바닥이 뚫린 .. [백준] 25215번 타이핑 [C++] https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 문제 설명 먼저 각 각 경우를 생각해야 한다. aaAaa 와 같이 소문자들 사이에 대문자가 1개 있을 경우, aaa★aa->6번만에 해결 가능 aa◆a◆aa->7번만에 해결 가능 aaAAa와 같이 소문자들 사이에 대문자가 2개 있을 경우, aaa★a★a->7번만에 해결 가능 aa◆aa◆a->7번만에 해결 가능 aAAAa와 같이 소문자들 사이에 대문자가 3개 있을 경우, aa★a★a★a->8번만에 해.. [백준] 25212번 조각케이크 [C++] https://www.acmicpc.net/problem/25212 25212번: 조각 케이크 조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다. www.acmicpc.net 문제 설명 접근 방법 조각 케이크의 갯수가 최대 10개기 떄문에 브루트포스 방식을 사용해 모든 경우의수를 찾아내도 자원소모가 크지 않다. 따라서 브루트포스 방식을 통해 각각 경우마다 케이크 조각들의 총 합이 101/100(1.01)을 넘어갈 경우에 더 탐색을 하지 않고, 총 값이 101/100 와 99/100 사이에 있다면 탐색을 하지 않고 결과값을 1 늘린다. 이러한 방식대로 모든 경우를 다 탐색하면 가능한 모든 경우를 찾을 수 있다. #include #include.. [백준] 25214번 크림 파스타 [C++] https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 문제 설명 접근 방법 먼저, 여태까지 나온 수 중 가장 작은수가 무엇인지를 구한다. 이를 위해서는 입력과 동시에 여태까지 나온 수 중에 가장 작은 수와 입력된 값을 비교하면 된다. 그 후에는 (현재 값- 가장 작은 값)이 여지껏 나온 결과 값 중에 가장 크다면 그 값을, 아니라면 이전의 나온 결과 값을 출력하면 된다. 코드 #include #include using namespace std; int.. [백준] 1516번 게임개발 [C++] https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 접근 방식 위상 정렬을 통해, 건물을 순서대로 지으면 된다. 순서대로 짓는 과정에서, 건물을 지을 때 의 최소 시간을 구하는 방식은 다이나믹 프로그래밍 기법을 사용하면 되는데 현재 건물까지 짓는 시간 = max(선행 건물 중 가장 오래 걸리는 건물) + 현재 건물을 짓는데 걸리는 시간 이라는 식이 세워지게 된다. #include #include #include using names.. [백준] 2482번 색 상환 [C++] https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 접근 방식 DP라는 이중 배열을 만들건데, DP[N][M]의 형태로 만든다. 여기서 N은 색상환의 갯수, M은 선택할 색상의 갯수이다. 처음에 두개의 예외처리를 해줘야 하는데, N개의 색 상환에서 1개의 색을 고른다고 가정해보자면, 경우의 수는 N개가 나온다. 따라서 M이 1일 때 DP[N][1] = N이라는 공식을 만족하게 된다. 문제에서 언급한 예시인데, 색상환의 갯수가 선택할 색의 2배보다 작을 경우, 선택할.. [백준] 4195번 친구 네트워크 [C++] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 접근 방법 각각의 문자가 들어올 때 map의 기능을 활용하여 , 이미 등록이 되어있는지 확인을 해준다. 이미 들어왔던 문자열이면 그 문자열의 value를 반환해주고, 새로 들어오는 문자열이면 새로운 value를 부여한 후 반환해준다. 이렇게 반환된 value들을 union find를 하여 연결을 시켜주면, 해결이 가능하다. union find의 과정에서 각각의 자식들의 갯수도 합쳐주는 .. [백준] 1948번 임계경로 [C++] https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 접근 방식 두가지 방법으로 풀어보았다. 시작점과 끝점에서 BFS 위상정렬 1. 시작점에서 BFS를 하여 목적지까지의 최대 거리와 각각의 지점까지 최대 거리를 구한다. 그 후 끝 점에서부터 다시 BFS를 하며, 현재까지의 거리 - 지나갈 간선 = 지나갈 곳의 거리 > n >> m; for (int i = 0; i .. 이전 1 2 3 4 다음
