전체 글(22)
-
백준 알고리즘 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