본문 바로가기

분류 전체보기

 (256)
[ 백준 14888 ] 연산자 끼워넣기 C++ DFS 풀이 # 문제링크 www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 이것도 삼성 기출이라는데 실버등급이다. 난이도가 복불복인가.. 암튼 숫자 위치는 바뀌지 않고, 연산자 위치만 바뀐다. 연산자의 개수가 최대 10개라서 그냥 모든 경우의 수를 계산해보면 된다. DFS로 구현했다. 문제 예시에서 경우의 수 60가지라고 했는데, 심심해서 한 번 모든 경우의 수를 출력해보았다. 제출 코드는 맨 아래에 있다. # 1 +..
[ 백준 14503 ] 로봇 청소기 # 문제링크 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제가 잘 읽히지 않아서 애를 먹었지만, 설명에 나온 그대로만 구현하니 패스가 되었네요. 로봇은 x, y 좌표와 방향을 저장할 수 있도록 struct 로 구성했고, 왼쪽으로 가는 방향이나 후진 방향 정하는 거는 그냥 배열로 적어주었습니다. 왼쪽으로 가는 방향은 그냥 -1 만 해줘도 되었을 것 같네요. # 제출 코드 #include using namespace std; int N, M; int ma..
[백준 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 처럼 가능한 부분을 쫘악 탐색해서 평균값으로 바꿔주면 된다.. 탐색이 더이상 진행되지 않으면 끝내고 답을 제출한다.. 처음에는 인구이동을 탐색이 끝나고 한 번에 진행하려고, 해당 정보들을 배열에 담아뒀었다. 근데 그렇게 하니까 배열을 한 번 더 돌아야 하는 단점도 있고, 정확하지 않아져서 (..??) 자꾸 ..

티스토리툴바