어흥

문제 링크: https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 처음에 비숍을 안넣는게 최선일 수 있다 - 체스판과 관련된 문제는 흑백으로 나눠서 생각하도록 한다 -> 시간복잡도가 줄어든다 2. 구현 - 백색 칸과 흑색 칸을 구분해서 흑색칸일 때 최대 + 백색칸일 때 최대를 구한다 - 해당칸이 비숍을 놓을 수 있는 칸인 ..

문제 링크: https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 1. 주의할 점 - 그래프로 생각 -> DFS로 접근 -> 중복된 숫자 처리 2. 구현 - 그래프로 생각하여 Arr[]배열..

문제 링크: https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 1. 주의할 점 - 부분수열의 합으로 만들어 지는 수에 대해 중복 처리가 필요하다(따로 값을 저장할 시) 2. 구현 - Set을 이용해 부분수열의 합을 저장한다 - Cal() 함수의 경우 부분수열로 만들 수 있는 모든 수를 Set에 저장한다 - Set의 N..

문제 링크: https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 www.acmicpc.net 1. 주의할 점 - DFS를 통해 구현이 가능하지만, 메모라이즈 기법과 함께 사용하지 않으면 TLE가 발생한다 - 메..

문제 링크: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시 www.acmicpc.net 1. 주의할 점 - 경로를 출력해야 하므로 역방향의 그래프도 저장해야 한다 - 경로를 찾는 방법은, 특정 조건..

문제 링크: https://www.acmicpc.net/problem/14369 14369번: 전화번호 수수께끼 (Small) 문제 "전화번호가 뭐에요?" "제 전화번호의 각 자리를 영어단어로 바꾸고, 철자를 잘 섞으면 OZONE TOWER가 나와요." "예?" "그리고 제 전화번호는 오름차순으로 정렬되어 있어요." "..." 입력 첫 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스에는 상대방이 제시한 스트링 S가 주어진다. S는 영어 대문자로만 이루어져 있다. 1≤ T ≤ 100이고, S의 길이는 3 이상 20 이하이다. 모든 테스트케이스에는 유일한 해답이 있다. 출력 www.acmicpc.net https://www.acmicpc.net/problem/14370 14370번: 전화번호 수수께..

문제 링크: https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 주의할 점 - DFS를 통해 해결한다 - 2000 X 2000 배열을 만들지 않고 List형태인 Vector를 사용한다 2. 구현 - 모든 Node를 시작점으로 각 지점까지의 거리가 4인 Node가 있다면 문제의 조건을 만족한다고 설정한다 - 모든 Node는 시작전에 시작점을 제외한 다른 Node의 Visit값을 False로 두고 시작한다. - 현재 Node와 연결된 다른 Node를 방문한 적이 없다면 그 Node로 이동한다 #include #include using namespace..

문제 링크: https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 1. 주의할 점 - DFS를 통해 10번이상 실행하지 않도록 설계한다. - 구슬이 겹쳐지는 경우 따로 처리한다 2...