문제 출처 https://www.acmicpc.net/problem/11049 정답 풀이 "행렬 곱셈 순서"는 dp를 이용해 푸는 전형적인 문제다. 최소 연산 횟수를 구하는 문제  행렬곱셈은 결합법칙을 따르기 때문에, 곱하는 순서에 따라 연산 횟수가 달라짐  문제 해결 전략 1. 행렬 곱셈 연산의 특징:  두 행렬 A (r1 x c1)와 B (r2 x c2)를 곱하면 새로운 행렬은 (r1 x c2)가 되고, 연산 횟수는 r1 * c1 * c2가 됩니다. 연산 순서를 바꾸면 그에 따라 필요한 곱셈 횟수가 달라집니다. 2. dp: DP 테이블을 사용하여 행렬을 곱하는 순서별 최소 연산 횟수를 저장합니다. dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 연산 횟수를 나타냅니다.정답 코..

문제 출처 https://www.acmicpc.net/problem/2138 정답 풀이 브루트포스와 그리디를 함께 이용한다. 첫번째 스위치를 클릭하는 경우와 클릭하지 않는 경우를 각각 확인한다.  풀이 접근 1. 첫번째 스위치 클릭 기준 :첫번째 전구의 상태를 바꾸면 나머지 전구의 상태도 다르게 변화하기 때문에 이를 기준으로 삼는다.  2. 그리디 :첫번째 스위치 선택 이후에는 두번째부터 차례대로 조작을 결정하여 목표 상태와 맞추어 나간다.  정답 코드 const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');const n = Number(input[0]);const initial = ..

문제 출처 https://www.acmicpc.net/problem/17281 정답 풀이  - 순열 함수로 타순을 정한다. - 정한 타순으로 모든 이닝을 거친 후의 점수를 구한다. - 각 점수중 최댓값을 출력한다.  정답 코드 //9명 //총 N이닝 //한 이닝에 3아웃 발생 => 종료 //타순 정함 (변경 x)//이닝 안끝났으면 다시 1번 타자 //이닝이 변경되도 이어서 타순 //이닝 시작할 때 주자 x //타순 정할 것 //1번 선수를 4번 타자로 미리 결정함 //return 가장 많은 득점let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const n = Number(input.shift()) con..

문제 출처 https://www.acmicpc.net/problem/17135 정답 풀이  simulation 함수는 주어진 궁수 배치에서 적을 제거하는 과정을 시뮬레이션하고, 제거된 적의 수를 반환합니다.combination 함수는 M열 중에서 3개의 궁수 위치를 선택하는 모든 경우의 수를 계산합니다.simulation에서 궁수의 사정거리에 있는 적을 탐색하고, 가장 가까운 적을 우선순위에 따라 공격합니다.시뮬레이션 결과를 바탕으로 궁수 배치 중 적을 가장 많이 제거할 수 있는 경우를 탐색합니다. 정답 코드 const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');const [N, M..

문제 출처 https://www.acmicpc.net/problem/1461 정답 풀이 - 양수와 음수를 따로 생각해줘야 한다. - 양수 배열과 음수 배열중 가장 절댓값이 큰 값을 나중에 total 에서 빼준다 => 가장 긴 거리를 가고 안돌아오는 것이 이득임. - 절댓값이 큰 책부터 처리해야함  정답 코드 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,m] = input[0].split(' ').map(v => +v); const place = input[1].split(' ').map(v => +v)let maxDistance =0; const negatives = place.fil..

문제 출처 https://www.acmicpc.net/problem/14500 정답 풀이 테트로미노 다섯가지 모양을 보면, dfs 탐색으로 커버 가능하다는 것을 알 수 있다. 단, ㅗ 모양 빼고 !  - 따라서 dfs 를 통해 cnt가 4가 될 때까지 탐색하고, - 최대 합을 구한다. - 따로, 'ㅗ','ㅏ',ㅜ'','ㅓ' 모양일 때 전체 합을 구한다. 정답 코드 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n, m] = input.shift().split(' ').map(v => +v); const graph = input.map(el => el.split(' ').map(v => +v..

문제 출처 https://www.acmicpc.net/problem/2589 정답 풀이 최단 거리 ? bfs 알고리즘을 사용하면 된다.  시작점이 어디냐에 따라 최단 거리가 달라지니까, for 이중 반복문을 통해 모든 L을 시작점으로 둔다.  그리고 bfs로 최대로 먼 곳을 갱신해준다. 정답 코드//상하좌우, 육지로 이동 //한 칸 이동 - 한 시간 걸림 //보물 : 최단 거리 이동하는데 , 가장 긴 시간이 걸리는 육지 두곳에 묻혀있음. //bfs 알고리즘 사용 //어디서 시작하냐도 중요해서 전체 L 들어가야함 //bfs로 탐색 후 그때의 max 값 구하기 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');..

문제 출처 https://www.acmicpc.net/problem/16724 정답 풀이 아래 그림과 같이 화살표를 무작위로 그려봤을 때, dfs로 탐색을 해서 해당 연결이 끝나는 곳에 safe zone을 두면 되겠다는 아이디어가 떠오른다. 그런데, visited 방문 처리로만 safe zone 을 다루면 안된다.  왜냐하면 파란색 애들은 이미 방문 처리로 끝나고, 주황색 애들이 남아버린다. 원래 같은 한 묶음이 될 수 있는데 ! 어떻게 위와 같은 경우에도 한 묶음으로 만들 수 있을까?  - dfs 반복문을 통해 사이클을 다 돈다.=> visited[x][y] = 2 로 처리해둔다. - 또 아직 방문하지 않은 곳 dfs 반복문으로 돈다. => 현재 돌고 있는 곳은 1로 처리, => 1로 처리하다가 만약 ..

문제 출처 https://www.acmicpc.net/problem/10159 정답 풀이 cnt1 = 해당 물건 보다 큰 물건의 개수를 센다. cnt2 = 해당 물건 보다 작은 물건의 개수를 센다. 답 = 전체 물건 개수 - cnt1 - cnt2 - 1(자기 자신) 개수를 세는 것은 dfs 탐색을 활용한다. 정답 코드  //무게 다른 물건 //1부터 N 번호 //각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건 개수 출력 //각 관계들을 2차 배열로 생성 및 정리 //dfs로 탐색 //각 숫자로 접근해서 cnt 하기 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')const n = Number(i..

문제 출처 https://www.acmicpc.net/problem/20058 정답 풀이 1. 그러니까, 주어진 grid를 크기에 따라 나누고 2. 그것을 회전한 후 3. 조건에 따라 얼음 -1 을 한다. 4. reduce 활용하여 모든 얼음의 합 5. dfs를 활용하여 가장 큰 덩어리를 출력  격자 회전 함수는 아래 블로그에 설명했다. https://fordang.tistory.com/352 격자 회전 함수 (90도 회전)1. 기본 개념 - grid : 회전해야 할 격자를 나타내는 2차원 배열- L : 격자를 나누는 단위의 레벨로, 2^L * 2^L 크기의 부분 격자로 나누어 회전한다. - size :  전체 격자의 크기 (size = 2^L)- 격자는 여러fordang.tistory.com 정답 코드..