본문 바로가기

Computer Science&Engineering

 (112)
[ 백준 15685 ] 드레곤 커브 # 문제링크 www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 처음에 읽고 나서, 어떻게 풀어야 할 지 전혀 감이 안왔던 문제다.. 저거를 어케 저케 돌리지? 요즘에는 어려우면 빨리 검색해서 접근법을 알아보는데, 결국 방향을 90도로 돌릴 때 규칙을 활용해서 푸는 문제였다. 각 뱡향이 있는 선분을 90도로 돌리면 방향이 +1씩 된다. 그리고 해당 방향을 저장해뒀다가 다음번 세대 돌릴 때 최근 추가된거부터 쭉쭉 체크해주면 된다. 90도..
[ 백준 14890 ] 경사로 / SWEA 활주로 건설 문제 # 문제링크 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이건 SW Expert Academy에서 풀었던 활주로 건설 문제와 같은 문제다! 한 번 풀었기 때문에 접근법을 알고있어서 금방 풀었다. 시뮬레이션 문제는 어렵다기 보다는.. 정신을 똑바로 차리는 게 가장 중요한 것 같다.. 일차원 배열 arr 을 하나 만들어서 한 줄씩 살펴보았다. 그렇게 모든 맵을 탐색하고 나서, 90도 회전해서 한 번 더 검사해준다. 그럼 세로 방향을 따로 만들지 않아도 된다.. # 제출 코드 #in..
[ 백준 14889 ] 스타트와 링크 C/C++ DFS # 문제링크 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이것도 Depth 가 최대 10이라서 DFS로 팀을 나눠주고, 팀 배정에 따라 map 에서 계산만 해주면 되는 문제였다. 근데 (1, 2), (3, 4) 이나 (2, 1), (4, 3) 이나 같은 팀이다. 이걸 생각도 안해보고 구현만 바로 해서 제출하니 시간초과가 났다. 테케 답은 맞게 나오니,, 원인도 제대로 모르고 괜히 배열 인덱스만 만져보다가 나중에 해당 원인을 알게 되었다. 그래서 중복 없는 조합으로 짜주었다. ..
[ 백준 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) 시간 안에 해결할 수 있을 거 같았다. 개껌이네 생각하고 노가다를 시작했다.. (역시 머리가 안좋으면 몸이 고생한다고 내 손이 고생했다.) 코테를 볼 때에도 머리가 안되면 재빨리 노가다라도 해서 통과..

티스토리툴바