📑  문제🌱 아이디어사자는 마주 보게 배치하면 안 되며, 한 마리도 존재하지 않는 경우도 하나의 경우의 수로 센다 동적계획법(DP)을 사용하면 시간도 아끼면서 풀 수 있다!사실 본인도 점화식 세우는 법을 잘 모른다... 하지만 감이 안 잡히면 N의 수만큼 경우의 수의 수열을 만들어 보자!일단 문제처럼  N*2 배열을 만들어보자! (문제 조건에 성립하는 경우의 수)N = 0 -> 1 N = 1 ->  3N = 2 -> 7N = 3 -> 17N = 4 -> 41 이렇게 증가되는 수열이 만들어진다 이것을 점화식으로 세운다면점화식 = fn = f(n-1)*2 + f(n-2) 이렇게 세울 수 있다. 즉 전값*2 + 전전값 이 현재값이다 이용해서 구현해 보자!🌱  코드 및 풀이점화식을 세우고 DP 통해 구현한..

📑 문제🌱 아이디어본문에서 "다리는 서로 겹칠 수 없다." 라는 조건이 하나 붙는데 이번 문제의 키 포인트이다."다리는 서로 겹칠 수 없다." 라는 말은 곧 순서를 고려하지 않는다 는 말과 같다.두 그림은 같은 사이트에 다리를 잇는 경우의 수이다. 순서를 고려한다면 두 경우는 서로 다른 경우가 되어야 한다.A, B, C != A, C, B 이 경우는 순서를 고려하기 때문에 요소가 같아도 순서가 달라 서로 다른 경우이다. 하지만 문제 조건 중 "다리는 서로 겹칠 수 없다." 를 성립하려면 위 두 그림은 같은 경우의 수가 되어야 한다!중복을 제거해야 하기 때문이다. 즉 A, B, C == A, C, B 이 성립되어야 중복이 제거가 되며 하나의 경우로 본다. 이 문제는 M개에서 N개를 뽑고 중복을 제거해야..

📑 문제 본문에서 "방향 없는 그래프가 주어졌을 때" 라는 말은 곧 양방향이다!즉 A -> B , B -> A 가 성립해야 한다. "연결 요소"에 대해 설명하기 위해 테스트 케이스를 두 가지를 가져와 봤다.1. 본문 예제 입력 1 위 사진은 본문에서 입력된 정점과 간선들의 그래프이다.왼쪽 집합 (1,2,5) 와 오른쪽 집합 (3,4,6)은 연결할 수 있는 간선이 없다 즉 "연결 요소의 개수는" 2 가 되는 것이다! 2. TestCase : 4 0이 경우는 노드는 4개이고 간선은 0이다 그렇다면 연결 요소의 개수는 몇일까?답은 4 이다. 간선이 없는 노드는 하나의 연결요소이다. 이점만 생각하고 구현한다면 쉽게 풀 수 있을 것이다. 🌱 코드 및 풀이ArrayList를 이용하여 인접리스트를 만들고 양방향임..

📑 문제  🌱 아이디어지도의 크기 (3 ≤ N, M ≤ 8), 입력되는 값이 적다! = 완탐 가능하다.지도의 최대 크기가 8*8 = 64 이다. 완전탐색 으로 풀 수 있다는 뜻이다,즉 지도에 벽을 3개를 모든 경우만큼 다 세운 후 가장 많은 안전구역의 크기를 구하면 된다!DFS, BFS 둘 다 사용해서 풀 수 있다DFS = 벽 세우기, BFS = 바이러스 퍼트리기 이렇게 역할을 나눠서 구현할 수 있다. 🌱 코드 및 풀이 엄청 길다;;; 하지만 각 기능을 함수로 나눠서 설명을 달아 놨으니 천천히 보신다면 이해하기엔 어려움이 없을 것이다아마도 이해가 안 된다면 댓글 달아주시면 최대한 설명해 보겠습니다.그래도 간단히 설명을 하자면 dfs() -> 지도에 벽을 3개를 세운다bfs() -> 바이러스를 전염시..

📑 문제🌱 아이디어N = 3, K = 1이라면 물병을 K개 이하로 만들어야 할 때 2L 물병 = 1개, 1L 물병 = 1개로 합 칠 수 있다. 하지만 아직 물병이 총 2개 이기 때문에 K개 이하로 만들기 위해 1L 물병 1개를 사서 2L 물병 = 2개 -> 4L 물병 = 1개로 만들어 조건 성립 시킨다.결국 같은 물량을 두 개씩 합친다 그렇다면 1L -> 2L -> 4L -> 8L로 물의 양이 정해진다이러한 규칙은 곧 이진수와 같다 그렇다면 비트마스킹으로 풀 수 있을 것이다! N = 3, K = 1 특히 N = 3을 이진수로 나타내면 11 이다. '1'의 개수가 K개 이하 여야 하기 때문에 N = 4를 이진수로 나타내면 100 이다 그러므로 4 - 3 = 1 즉 1개만 물병을 추가하면 된다. 🌱 코..