SanbonDeveloper

문제 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" ? "..

문제 21315번: 카드 섞기 마술사 영재는 카드 더미를 이용한 마술을 개발하였다. 카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다. 영재는 마술을 www.acmicpc.net 풀이 완전 탐색으로 2개의 k값을 찾는 컨셉 자체는 쉬웠는데 카드를 섞을 때 큐를 사용하지 않고 구현하는 방식이 까다로웠다. range(카드를 뺄 수 있는 범위), count(빼야되는 개수)를 통해 섞을 범위를 정해준다. 해당 범위에 속하는 모든 카드를 새로운 카드 배열에 옮겨주고 해당 위치는 0으로 설정한다. 다시 새로운 카드 배열에 있는 값을 기존 카드 배열로 옮겨준다. 소스 코드 const filePath = process.platform === "linu..

문제 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀이 N의 범위가 크지 않기 때문에 무식하게 완전 탐색으로 풀 수 있다. board의 모든 인덱스를 탐색하며 꽃을 심을 수 있는 곳을 찾는다. (dfs + 꽃 구조에 해당하는 위치 확인) 꽃을 심을 수 있으면 해당 구역의 visited를 true로 설정하고 다음 위치를 찾는 과정을 반복한다. (dfs) 재귀에서 빠져나올 때 반드시 해당 구역의 visited를 false로 설정한다. (추후 다시 사용해야 한다.) 소스 코드 const filePath = pr..

문제 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const [N, M] = input[0].split(" ").map(Number); const board = Array.from({ length: N }, ..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 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() { retu..

문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 가장 왼쪽 열과 가장 오른쪽 열을 제외한 모든 열에서 해당 위치를 기준으로 왼쪽에서 가장 많은 블록의 개수와 오른쪽에서 가장 많은 블록의 개수를 구한다. 그 중에서 더 작은 값에 현재 위치의 블록의 개수를 감소시킨다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSy..