https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. Logic 입력을 받은 후 물건이 있는 좌표를 받으면 0~5까지의 char타입으로 변경해서 넣어줬다. BFS를 돌면서 입력 받을 때 char타입으로 변경해서 넣어준 물건을 만나면 다시 int타입으로 변경해서 shift연산을 통해 비트계산을 해서 몇번째 물건을 집었는지 기록한다. BFS를 돌면서 E(출구)를 만났을 때 내가 받은 물건과 도착한 시점에서의 물건갯수가 일치하면 걸린시간을 리..
Algorithm
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. Logic 열쇠가 6개밖에 없기때문에 비트로 표현 가능하다. 큐에 현재 열쇠를 모은 상태를 비트로 저장해서 관리해준다. 이 문제에서 나눠질 부분문제를 생각해보면 1. 열쇠를 만날경우 - 현재 열쇠를 모은거와 지금 열쇠를 or연산하여 모은 상태를 구하고 모았던 열쇠면 다시 갈 필요 없기 때문에 건너뛰고 안모은 열쇠면 갱신한 열쇠 컬렉션 상태를 큐에 넣어준다. 2...
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. Logic 구현은 어렵지 않은문제인데 실수하기 쉬운 문제인 것 같다. 1. 입력을 받고 공기청정기가 있는 위치의 y좌표를 저장해둔다. 2. 미세먼지의 합을 더할 임시 배열에 먼지를 /5한 값을 4방향으로 더해준다. 3. 이전 먼지 배열과 임시배열을 더해줌과 동시에 0으로 초기화해준다. 2. Code #include using namespace std; int r, c, t; int dust..
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. Logic 부분문제를 나눠보자면 1. 오름차순으로 받는경우 1-1. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 큰경우 > 선택 1-2. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 작은 경우 > 내림차순으로 변경하고 선택 2. 내림차순으로 변경된 경우 2-1. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 작은경우 > 선택 3. 선택안하고 인덱스를 넘기는 경우 2. Code #include using names..
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. Logic 대표적인 백트래킹 문제. 문제를 푸는 로직은 아래와 같다. 1. 입력을 받으면서 0의 갯수(채워야 하는 빈칸의 갯수)를 같이 카운트한다. 2. solve함수의 파라미터로 0을 넣고 스도쿠 칸이 총 81칸이기 때문에 나누기, 나머지 연산자로 y, x칸의 좌표를 구한다. 나눗셈 연산 : y, 나머지 연산 x 3. 가로, 세로, 3*3에 이미 나온 숫자들이 있는지 확인하고 1~9까지 돌..
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 1. Logic 1. 파이어볼을 이동시킨다. 이떄 참조자를 통해 파이어볼의 x, y좌표를 계산해서 변경한 후 임시 그래프에 넣어준다. 2. 파이어볼 이동이 끝나면 합쳐줘야한다. 모든 파이어볼의 방향이 짝수거나 홀수면 0,2,4,6으로 가야하기 떄문에 홀짝을 bool로 판단한다. 3. 홀짝 판단 여부를 가지고 방향을 정해서 다시 임시 벡터에 넣어준다. 4. k..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. Logic 고슴도치는 물로 찰 예정인 곳은 못가기 떄문에 고슴도치 이동보다 물 이동을 먼저 해줘야 한다. BFS두번 돌려주고 while(true)문 탈출하기 위해 옮겼는지만 확인해서 탈출만 잘 해주면 된다. 2. Code #include using namespace std; const int INF = 0x3f3f3f3f; int r, c; int sy, sx; int goalY, goalX; int d..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. Logic 주어진 규칙에 맞춰 그대로 구현하면 됨. 뱀의 머리와 길이까지의 좌표를 저장하는 덱을 생성해서 넣다뺐다 해주면 됨. 1. 덱에 다음에 머리가 갈 좌표를 front에 넣어줌 + 이동 횟수 1 올려주기 2. 게임에서 지게되는 조건 확인 3. 머리가 이동한 곳 방문 처리하여 뱀이 있는곳 표시(이걸 2번보다 먼저하면 항상 게임에서 지게되는 조건이 만들어짐) 4. 머리가 이동한 곳에 사과가 없으면..
https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. Logic 유니온 파인드를 사용해서 입력받은 노드를 연결해준다. merge를 하게되면 서로의 root노드가 정해진다. 이 root노드가 같은 것 끼리 연결하게 되면 사이클이 생긴다. 즉 merge하기 전 부모 노드를 찾고 이후에 서로의 루트 노드가 같으면 사이클이 있기 때문에 출력해주고 루트 노드가 다르면 merge 해준다. 2. Code #include using namespace s..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 1. Logic 낚시꾼이 물고기를 잡고 그 이후에 상어가 이동을 한다. 함수 로직 순서는 이렇고, 이 문제를 풀면서 두번 막혔는데 두개만 잘 생각하면 풀기 쉬운 문제인 것 같다. 두개를 생각하는게 어려워서 그렇지,, (내 기준) 1. 배열은 0부터 시작한다. 아주 기초적이지만 이거때문에 상어를 이동하는 로직에서 한번 틀렸다..ㅜ 답이 이상해서 출력해보다가 테케 1번의 3번상어가..
