본문 바로가기

분류 전체보기

 (254)
[백준 14502] 연구소 C++ # 문제링크 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 비슷한 문제를 풀어봐서 금방 풀었다. map 크기는 8 * 8 이 최대고, 세울 수 있는 벽은 세 개이다. 맵이나 depth가 이렇게 작으면 노가다로 풀어도 된다. 1) map 에서 0인 좌표 중에 벽을 세울 위치 세 군데를 DFS로 고른다. (chk배열에 true로 체크) 2) 해당 위치에 벽을 세워주고 바이러스 위치부터 BFS를 돌린다. map에 직접 바이러스(2) 표시를 한다. 3) 이후 안전한 공간의 개..
[백준 14501] 퇴사 C++ # 문제링크 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 삼성 기출 문제집에서 문제를 하나씩 풀고 있다. 대부분 골드 난이도의 문제였는데,, 이건 실버 난이도다. 제발 이런 문제가 하나 나왔으면 좋겠다.. DFS 기본 문제 느낌이다.. # 제출 코드 #include using namespace std; int N; int map[16][2]; // 0은 time, 1은 pay int ans; void DFS(int start, int pay) { if (pay > ans) ans = pay; for (int i = start; i N + 1) continue; DFS(i + map[i][0]..
[백준 14500] 테트로미노 C++ 노가다풀이 # 문제링크 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net DFS 등등 활용해서 계산할 수도 있겠지만 문제를 보니 경우의 수가 몇 가지 되지 않을 것 같았다. 누적합을 활용해서 직접 모든 경우의 수를 직접 구해줘도 되지 않을까 하는 생각이 들었고, O(n^2) 시간 안에 해결할 수 있을 거 같았다. 개껌이네 생각하고 노가다를 시작했다.. (역시 머리가 안좋으면 몸이 고생한다고 내 손이 고생했다.) 코테를 볼 때에도 머리가 안되면 재빨리 노가다라도 해서 통과..
[백준 3055] 탈출 c++ # 문제링크 www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 매 분마다 고슴도치도 네 방향으로 움직이고, 물도 네 방향으로 움직이니까, queue를 두개 만들어주고 각각 돌도록 구현했다. 유의할 점은 Flooding 함수에서 stime과 time 을 비교하여 같지 않으면, 큐에서 pop을 해주면 안된다. 습관적으로 front()를 확인하고 pop()을 해주었는데, 조건이 맞지 않으면 pop()을 해주지 말아야 한다. 또 하나 기억할 점은 테스트 케이스를 여러 개 돌릴 때..
[백준 12100] 2048 (Easy) C++ # 문제링크 www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 잘 푼 것 같은데 채점에서 광탈하길래 우울했던 문제.. 원인은 freopen() 을 지워주지 않아서였다 ㅠㅠㅠㅠㅠㅠ 그것도 모르고 왜 틀렸는지 몇 시간 더 뜯어보면서 스트레스 받았다.. 문제를 처음 읽고, "최대 5번" 이동시켜서 얻을 수 있는 가장 큰 수를 구하는 것이기 때문에, 모든 경우의 수를 다 구해봐도 괜찮겠다고 생각했다. (배열의 크기도 20*20 밖에 되지 ..
[백준 16234] 인구이동 # 문제링크 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 국경선을 공유하는 두 나라라고 해서 바로 BFS를 떠올렸다. Floodfill 처럼 가능한 부분을 쫘악 탐색해서 평균값으로 바꿔주면 된다.. 탐색이 더이상 진행되지 않으면 끝내고 답을 제출한다.. 처음에는 인구이동을 탐색이 끝나고 한 번에 진행하려고, 해당 정보들을 배열에 담아뒀었다. 근데 그렇게 하니까 배열을 한 번 더 돌아야 하는 단점도 있고, 정확하지 않아져서 (..??) 자꾸 ..
[백준 3190] 뱀 C++ # 문제링크 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net C++의 deque 를 사용해서 풀었다. 앞으로 갈 때는 push_front() 해주고, 사과가 없을 때는 pop_back() 해주었다. 방향은 이차원 배열을 만들어서 해결했다. dir[i][k] 배열은 현재 i 방향일 때 k (왼쪽이나 오른쪽)으로 움직이는 방향이다. 잘 하시는 분들은 뭔가 방향 이동에서도 규칙성을 찾으시겠지만, 나는 그냥 배열로 다 써주었다.. 앞으로 갈 때마다 벽이랑 부딪혔는지, 자기..
[백준 16236] 아기상어 C++ # 문제링크 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS로 같은 거리를 탐색합니다. 탐색하다가 먹을 수 있는 물고기가 나오면 vector 에 넣어뒀다가, 같은 거리탐색이 끝나면 vector 중에서 물고기를 골라서 먹고, 아기상어 위치를 해당 물고기 위치로 옮겨서 다시 탐색을 시작합니다. # 제출 코드 #include #include #include #include #include #include using namespace std; stru..

티스토리툴바