https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제조건 연결된 4개의 정사각형 블록으로 모양을 만든다. 만들어진 모양을 종이위에 올렸을때, 4개의 숫자의 합의 최댓값은? 접근방법 완전탐색을 위해서 brute force로 접근해봤다. 그래서 전체 map을 돌면서 DFS를 수행할 수 있도록 구현했다. #include using namespace std; int n, m, map[501][501], visited[501][501]; int dy[]..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제조건 n개의 시험장 각 시험장의 응시자 수(a) 총감독관이 감시할수 있는 수(b), 부감독관이 감시할수 있는 수(c) 총감독관은 시험장마다 오직 1명만 가능 너무 쉽게 생각했는데, 처음부터 틀려버렸다. 예외 조건이라고는 총감독관 혼자서 응시자를 모두 감시할 수있을경우에 대한 로직만 처리하면 될 줄 알았는데, 뭐가 문제인지 몰랐다. 생각해..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제조건 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 접근방법 먼저 자료구조 queue가 떠올랐다. 사과가 없다면 꼬리부분을 계속삭제해야하므로,..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제조건 N x M 크기의 보드가있다. 빨간공과, 파란공이 각 하나씩 있다.(위치 주어짐) 공을 내보낼수있는 구멍이 하나 있다.(위치 주어짐) 보드를 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 이 동작만으로 공을 움직여서 빨간공만 구멍으로 빼야한다. 빨간공, 파란공은 항상 같이..

https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제조건 아래(↓), 오른쪽(→), 오른쪽아래(↘)로 갈수 있는 불도저가있고, 오른쪽 맨 아래칸까지 이동한다. A(불도저 아래쪽, 사과), B(불도저 위쪽, 바나나) 사과와 바나나의 합의 최댓값의 경우는? 처음 문제를 봤을땐, 탐색을 진행하는 경우의 수인것같아서 BFS로 접근했다. 하지만 이 접근방법은 최소일때 구하기 용이한 방법으로 생각을 좀더 했다. 우선 Brute Force를 떠올렸는데, ..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제조건 주식하나 사고, 팔고, 아무것도 안하는 것중 하나만 할 수 있다. 각 날마다의 주가가 주어지고, 조건 1 을 반복하면서 최대이익을 구한다. 이 문제는 예시로 시작하는 것이 편할거 같다고 생각한다. ex) 날 별로 주가가 3, 5, 9일 때 : 3, 5 두 날 전부 주식을 사고, 9일때 주식을 팔면된다 산금액 : 8(3x1 + 5x1) 판금액 : 18(9 x 2) 최대이익 : ..

https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 문제조건 플레이어가 입장을 신청하였을 때 매칭이 가능한 방이 없다면 새로운 방을 생성하고 입장시킨다. 이떄 해당 방에는 처음 입장한 플레이어의 레벨을 기준으로 -10부터 +10까지 입장 가능하다. 입장 가능한 방이 있다면 입장시킨 후 방의 정원이 모두 찰 때까지 대기시킨다. 이때 입장이 가능한 방이 여러 개라면 먼저 생성된 방에 입장한다. 방의 정원이 모두 차면 게임을 시작시킨다. 먼저 입력을 받으면..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제조건 두개의 전봇대가 있고, 서로 교차하지않게 전깃줄이 이어지도록 하는 경우일때의 제거해야할 전깃줄 개수와 A전봇대에서의 제거되는 번호 같은 위치에 두개이상의 전깃줄이 연결될 수는 없다. 완전탐색으로 풀려고 시도하면 전깃줄으 개수가 10만개이므로, n^2는 시간초과가 날 것이다. 따라서 어떤 접근법으로 가면 시간을 단축시킬수 있을까 생각해봤다. 이진탐색으로 접근하는 방법인데 다행히도, al..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. 첫번째로 구해야할것은 LCS의 길이이다. 나는 완전탐색으로 두 문자열을 돌면서 dynamic ..

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제조건 어떤 문자열을 팰린드롬으로 분할한다. 분할된 수의 최솟값을 출력 팰린드롬이란? 어떤 문자가 있을때, 거꾸로 뒤집어서 읽어도 똑같은 문자를 의미한다. ex) 기러기 ☞ 기러기(O) cf) 거북이 ☞ 이북거(X) 이 문제에서 핵심은 문자가 입력으로 들어왔을때, 문자열안에서의 모든 경우의수를 탐색해서 팰린드롬인지 각각 파악해야..