CODING(18)
-
백준 알고리즘 14889_스타트와 링크 C++
문제 (링크)14889번: 스타트와 링크 (acmicpc.net) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 사고과정 정답률은 높은데 나는 어려웠다. 팀을 어떻게 나누느냐가 관건인데다 재귀를 사용하지 않고 풀려고 했더니, 어떤 방법으로 팀을 나눠야할지는 생각은 했는데 구현하기가 너무 귀찮을 것 같아서 그냥 재귀를 이용하기로 했다. 제일 먼저 생각한 것은 팀1에 0번 선수를 고정해 놓는 것이다. 0번 선수를 기준으로 팀을 나눈다면 어쩄든 모든 경우의 수를 탐색할 수 있기 때문이다. 다음은 어떤 방법으로 선수를 1번팀에 넣고 나머..
2021.02.10 -
백준 알고리즘 14890_경사로 C
문제 (링크) 14890번: 경사로 (acmicpc.net) 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 사고과정 처음 문제를 봤을 때, 조금 복잡하다고 생각했다. 문제 길이도 길 뿐더러 처리해야할 조건이 각 줄에서 초기화 되어야하기 때문이다. 그리고 독해력이 딸린건지 문제조건이 잘 안들어오기도 했다. 제일 헷갈렸던 점은, 각 보행로를 만들 때 사용한 경사로는 다시 제거가 되는건지, 교차지점에서 영향을 주는건지가 였다. 이 것은 예시 입력 아래에 있는 힌트를 보면 각 보행로를 만들 때만 존재하는 경사로라는 것을 알 수 있다. 위 ..
2021.02.09 -
백준 알고리즘 14888_ 연산자 끼워넣기 C
문제 링크(14888번: 연산자 끼워넣기 (acmicpc.net)) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 사고과정 문제를 읽을 때 주의해야 하는 문제다. 처음 입력받은 숫자의 순서는 바뀌지 않고 연산자들의 순서만 바꾸면 된다. 즉 연산자들의 "중복이 있는 순서 세우기"이다. 문제는 어떻게 그 순서를 정할 것이냐는 것. 처음에 생각한 것은 연산배열을 선언해 숫자로 대치된 연산자를 저장해 모든 조합을 저장하는 것이다. 하지만 노력과 시간에 비해 결과..
2021.02.07 -
백준 알고리즘 14503_로봇 청소기 C
문제 (링크)14503번: 로봇 청소기 (acmicpc.net) 사고과정 처음 문제를 봤을 때 전형적인 DFS문제라고 생각했다. 현재 위치를 기준으로 4방향을 탐색한 뒤 새 위치를 업데이트하기 때문이다. 하지만 결과적으로 DFS문제는 아니고 비슷한 방법을 사용해서 풀이할 수 있는 문제이다. 문제를 해결하기 위해 난 문제 흐름대로 방법을 생각했다. 현재 위치(r,c)와 dir가 주어진 상태에서 반시계방향으로 4번, 다시 현재 방향을 바라볼 때까지 반복하는데, 만약 청소를 할 수 있는 칸이 있다면 탐색을 멈추고 해당 칸으로 이동한다. 이후 탐색을 반복한다. 이 때, 4방향 모두 방문(청소)했거나 벽이면 주어진 dir의 바라보는 상태로 후진을 하고 탐색을 시작한다. 후진도 불가능하면 코드를 끝낸다. DFS와 ..
2021.02.07 -
백준 알고리즘 14501_퇴사 C
문제 (링크) 14501번: 퇴사 (acmicpc.net) 사고과정 문제를 보자마자 '아 DP인가?' 싶었다. 이 것도 dp라고 해야하는지는 잘 모르겠지만 어쨌거나 각 날짜에서 받을 수 있는 상담비를 최댓값으로 갱신하며 탐색하면 될 것 같았다. 내코드 #include #include int main() { int N,i; scanf("%d", &N); int** task = (int**)malloc(N * sizeof(int*)); int* earn = (int*)calloc(N, sizeof(int)); for (i = 0; i < N; i++) { task[i] = (int*)malloc(2 * sizeof(int)); } for (i = 0; i < N; i++) { scanf("%d %d", &t..
2021.02.04 -
백준 알고리즘 14502_ 연구소 c++
문제 (링크) 14502번: 연구소 (acmicpc.net) 사고과정 이 문제는 정답률에서 볼 수 있듯 그리 어려운 문제는 아니다. 처음 문제를 봤을 때 생각했던 것은 어떻게 하면 효율적으로 코드를 짤 수 있을까였다. 그래서 생각보다 문제를 푸는데 오래 걸렸다. 원래는 C만 이용해서 풀려고 했는데 map 배열을 각 단계에서 수정하지 않고 사용하고 싶어서 c++의 이중 vector를 사용하기로 했다. 문제를 푸는데 3가지 단계로 분할했다. 1. 문제에서 벽을 꼭 3개 설치한다 했으니, 아무 것도 없는 공간 중 3개의 벽을 임의로 고른다 2. 벽을 세운 후 바이러스를 퍼뜨린다. 3. 바이러스가 모두 퍼진 후 안전구역의 칸을 구한다. 이 중 가장 생각을 많이 한 것은 첫 번째 단계이다. 육안으로 볼 땐 대충 ..
2021.02.04