문제 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 시간복잡도가 40 * 40 * 100 * 4 으로 충분히 완전 탐색으로 풀 수 있는 문제였다. 노트북와 스티커를 비교할 때 스티커가 노트북의 범위를 벗어나지 않도록 범위를 지정해준다. 스티커의 값도 1이고 노트북의 값도 1이면 해당 위치에 스티커를 붙일 수 없다. 스티커의 세로의 길이와 가로의 길이가 다를 수 있기 때문에 회전 시 세로의 길이와 가로의 길이를 스왑해준다. 소스 코드 const filePath = process.platform === "li..
문제 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net 풀이 N과 W의 범위가 크지 않다고 생각해서 조합 알고리즘을 통해 구현했고 다행히 시간초과가 발생하지 않았다. 하나의 전공서적 이름의 문자를 탐색하여 찾는 단어가 있으면 제거하고 다음 dfs로 이동한다. 단어의 모든 문자가 제거된 경우 최소 가격을 갱신하고 dfs를 종료한다. 자바스크립트에서 배열은 참조값이라서 원본 배열을 훼손시키지 않기 위해 깊은 복사를 수행했다. 소스 코드 const filePath = process.platform === "linux" ?..
문제 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 소스 코드 class Queue { constructor() { this.dat = []; this.head = 0; this.tail = 0; } push(item) { this.dat[this.tail++] = item; } pop() { this.head++; } front() { return this.dat[this.head]; } rear() { return this.dat[this.tail - 1]; } isEmpty() { ret..
문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 소스 코드 class Queue { constructor() { this.dat = []; this.head = 0; this.tail = 0; } push(item) { this.dat[this.tail++] = item; } pop() { this.head++; } front() { return this.dat[this.head]; } rear() { return this.dat[this.tail - 1]; } isEmpty() { return this.head ==..
문제 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 소스 코드 class Queue { constructor() { this.dat = []; this.head = 0; this.tail = 0; } push(item) { this.dat[this.tail++] = item; } pop() { this.head++; } front() { return this.dat[this.head]; } rear() { return this.dat[this.tail - 1]; } isEmpt..
문제 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 풀이 N이 최대 20이라 팀이 될 수 있는 모든 조합을 완전 탐색으로 풀 수 있을까 걱정했는데 완전 탐색으로 풀 수 있는게 신기했다. dfs의 인수로 전달되는 cnt를 하나의 직원의 번호로 생각하여 구현했다. dfs를 한번 돌릴 때 해당 직원이 스타트 팀(true)과 링크 팀(false)가 되는 경우를 모두 수행했다. 하나의 팀에 0명 있는 경우를 예외 처리해주지 않은 이유는 그 때의 값은 최솟값이 될 수 없기 때..
문제 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 숫자는 항상 왼쪽에서 오른쪽, 위에서 아래로 수를 이어붙인다. 하나의 칸 당 가로에 속하는 경우와 세로에 속하는 경우를 구해준다. boolean으로 가로에 속하는 경우와 세로에 속하는 경우를 표시해줄 수 있다. 하나의 행에 대해 모든 열의 탐색이 끝나면 행을 증가시키고 모든 행을 탐색했을 때 최댓값을 갱신해준다. calc함수에서는 2중 for문을 2번 돌면서 가로로 잘린 숫자와 세로로 잘린 숫자를 구해 더해준다. 소스 코드 const filePath ..
문제 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 문제를 보자마자 순열 알고리즘으로 풀어야겠다고 생각했다. 그런데 한번의 dfs에서 8가지 케이스를 각각 구현해야 하는 엄청난 노가다가 요구되는 문제였다. (최대한 중복을 제거하려 노력했다.) 이 문제의 핵심은 예를 들어 1행을 첫번째 dfs에서 뒤집는 경우랑 3번째 dfs에서 뒤집는 경우랑 결과가 다르다는 것이다. (그래서 순열 알고리즘으로 구현) 인터넷에 찾아보니까 비트마스킹으로 구현하는 방법도 있는듯 하다. 소스 코드 const filePat..
문제 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 풀이 코드 구조를 신경쓰지 않고 풀 수 있는 방법이 생각이 났는데 깔끔하게 구현하고 싶어서 해당 방법을 사용하지 않았다. 문자열인 수식을 순차적으로 탐색하며 상황에 맞게 idx를 증가시킨다. dfs를 수행할 때 '괄호로 묶은 경우'와 '괄호로 묶지 않은 경우'를 모두 수행해준다. 이전 수식과 계산을 연결할 때와 괄호를 묶어 계산할 때 calc함수를 재사용했다. 최댓값이 음수가 될 수 있기 때문에 answer의 초기값을 -Infinity로 설정했다..
문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 N의 최댓값이 10이므로 바로 조합 알고리즘으로 풀면 되겠다고 생각했다. S는 곱이기 때문에 1으로 시작하고 B는 합이기 때문에 0으로 시작한다. 한번 재귀를 돌 때마다 계속 현재 신맛과 쓴맛의 차에 최솟값을 확인한다. 요리 재료는 무조건 1개 이상 사용해야 되므로 cnt를 통해 개수가 1개 이상일 때만 최솟값을 확인하게 구현했다. 소스 코드 const filePath = process.platform === "linux" ? "..
