yulee

🤔문제 이해 각 퀘스트당 필요한 스킬을 다 사용가능할 때 그 퀘스트를 깰 수 있다. 2n개의 스킬 중 n개만 골랐을 때 최대로 많이 깰 수 있는 퀘스트의 개수를 출력하면 된다. 조건 키의 개수 : n 퀘스트의 개수 : m (1 ~ 100) 퀘스트 당 스킬 수 : k (1 ~ n) 스킬의 번호 ( 1~2n) 🔥풀이🔥 2n개의 스킬 중 배치할 스킬 n개를 골랐을 때 깰 수 있는 퀘스트의 개수 중 가장 큰 값을 출력하게 했다. 변수 - quest[i] : i번째 퀘스트에서 필요한 스킬의 번호를 비트로 표현 재귀함수 void Solve(int i, int d, int cnt) - 현재 상태 : 현재까지 정한 스킬을 비트로 나타내는 i, 몇번째 스킬까지 처리해줬는지를 나타내는 d, 정한 스킬의 개수 cnt - 다..

🤔문제 이해 행과 열, 그리고 3x3의 작은 사각형 안에 1~9까지의 수가 중복없이 나오게 보드를 짜는 문제이다. 조건 보드 : 9 x 9 시간 : 2초 메모리 : 256MB 🔥풀이🔥 백트래킹 방식으로 값이 비어있는 부분에 넣을 수 있는 수 중에서 가장 작은 수부터 넣어보면서 처음으로 보드가 숫자로 다 채워질 수 있을 때를 출력하면 된다. 변수 - bool width[i][num] : i번째 행에 num의 존재 유무 - bool length[i][num] : i번째 열에 num의 존재 유무 - bool square[i][num] : i번째 사각형에 num의 존재 유무 - square의 경우 좌표가 (i, j)일 때 (i/3)*2 + (j/3)을 계산한 값이 몇번째 사각형인지 나타낸다. 재귀함수 solve..

🤔문제 이해 진실을 알고 있는 사람들이 파티에 참석하는 경우 그 파티에선 진실만 말해야하고, 순서 상관없이 진실을 한번이라도 듣게 되는 사람들이 참석하는 파티는 진실만 말해야 할 때 과장된 이야기를 할 수 있는 파티의 개수를 구하면 되는 문제이다. 💡첫번째 아이디어 진실을 아는 사람이 포함된 파티에 간 사람들을 모두 진실을 알고 있다고 처리해주고 이 과정을 반복하면 진실로 말해야 하는 파티와 과장해서 말해도 되는 파티를 구분해줄 수 있다고 생각했다. 🔥풀이🔥 know[i] : i번 사람이 진실을 알면 true, 모르면 false party_know[i] : i번 파티가 진실을 말해야 하는 파티면 true, 과장해서 말해도 되는 파티면 false party[i][j] : i번째 파티에 참석한 사람들의 번호..

🤔문제 이해 상어는 주어진 속도와 방향으로 1초마다 이동하고, 같은 위치에 두마리 이상이 이동된 경우 사이즈가 큰 상어만 남게 된다. 낚시왕도 1초마다 오른쪽으로 이동해 낚시왕이 위치한 열에 있는 상어 중 가장 위에 있는 상어만 잡아 올리고 잡은 상어의 크기를 모두 합한 값을 출력하는 문제이다. 💡첫번째 아이디어 단순하게 구현하는 문제인데 시간이 적게 걸리게 하기 위해서는 상어를 이동시킬 때 격자판의 경계를 만났을 때마다 방향을 바꾸는게 아닌 한번에 옮기는 식을 세워야 한다고 생각했다. 여러 경우를 시뮬레이션 해보고 식을 세웠다. 🔥풀이🔥 격자판의 크기를 넘어간다면 처음 넘어가고 그 이후부터는 (격자판 크기-1)로 나눈 나머지가 규칙적으로 0, 1, ... (격자판 크기 -1) , ...,1, 0이 되게..

🤔문제 이해 먼저 푸는 게 좋은 문제는 먼저 풀어주되 번호가 낮은 문제를 더 우선적으로 풀면 된다. 출력으로는 문제 푸는 순서를 출력하면 되는 문제이다. 💡첫번째 아이디어 먼저 푸는 것이 좋은 문제가 있는 문제를 모두 순서대로 출력해주고, 나머지 문제들을 오름차순으로 출력해주면 된다고 생각했다. ❌첫번째 제출 제대로 풀었다고 생각했고, 출력 값도 잘 나왔다.문제를 다시 읽어보고 반례를 생각해보니 문제의 조건에 "가능하면 쉬운 문제부터"라는 조건을 빠뜨렸었다..! 💡두번째 아이디어 먼저 푸는 것이 좋은 문제가 없는 문제의 in_degree도 0으로 초기화해서 가능하면 쉬운 문제들부터 출력되게 해주었다 . 🔥풀이🔥 위상정렬 알고리즘을 이용하였다. 우선순위큐를 사용하여 in_degree가 0인 문제 먼저 출력..

🤔문제 이해 연속된 몇 개의 수를 선택했을 때 그 합이 가장 큰 수열의 합을 출력하는데 그 수열 중에서 하나를 없앨 수 있는 문제이다. 💡첫번째 아이디어 하나를 어떻게 없앨까 하다가 바로 전에 푼 가장 긴 바이토닉 부분 수열이 떠올랐다. 앞에서 순서대로 합이 가장 큰 연속합1을 구해주고, 뒤에서 순서대로 합이 가장 큰 연속합2을 구해주고 어느 숫자를 기준으로 양옆으로 연속합1과 2를 더한 값이 가장 크다면 그 기준 숫자를 없앤 것이 더 큰거고, 연속합1의 최댓값이 가장 크다면 하나를 없애지 않아도 가장 큰 연속합을 구할 수 있는 것이라고 생각해서 풀었다. 🔥풀이🔥 dp[i]는 i번째 수를 마지막 수로 했을 때 가장 큰 연속합을 의미한다. dp2[i]는 i번째 수를 첫번째 수로 했을 때 가장 큰 연속합을 ..

🤔문제 이해 어느 한 숫자를 기준으로 왼쪽에는 감소하는 숫자들이, 오른쪽에는 증가하는 숫자들이 오는 부분 수열을 찾는 문제이다. 이때, 같은 숫자가 연속적으로 나올 수 없다. 💡첫번째 아이디어 가장 긴 증가하는 부분 수열의 응용 버전이었다. 🔥풀이🔥 dp_in[i]는 i번째 수를 마지막 수로 했을 때 증가하는 수의 개수를 의미하고, dp_de[i]는 i번째 수를 첫번째 수로 했을 때 감소하는 수의 개수를 의미한다. 1. dp_in과 dp_de는 모두 1로 초기화한다. 2. 앞에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_in과 이전값 dp_in에 1을 더한 값 중에서 더 큰 값을 dp_in의 현재값에 넣어준다. 3. 뒤에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_de..

🤔문제 이해 i+1번째 수가 i번째 수보다 큰 부분 수열 중에서 가장 긴 수열의 길이를 출력하는 문제이다. 💡첫번째 아이디어 처음엔 부르트 포스가 생각났다. 그냥 눈으로 계산해봐도 모든 조합을 생각해봐야 풀린다고 생각했기 때문이다. 근데 저걸 처음부터 모든 조합을 다 계산하게 되면 1초는 거뜬히 넘기게 된다... 💡두번째 아이디어 멘토님에게 LCS(longest increasing subsequence)를 푸는 방법을 전수받았다! 풀이에 자세히 설명하겠다. 🔥풀이🔥 입력받은 수열은 arr에 순서대로 저장해놓고 dp 배열을 arr값으로 초기화해준다. 수열의 두번째 수부터 n번째 수까지를 나타내는 인덱스 i와 첫번째 수부터 i번째 수까지를 나타내는 인덱스 j가 있다고 하자. 만약 arr[j]가 arr[i]보..

🤔문제 이해 나라를 세운 사람이 1 왕족이고, 왕족이 아닌 외부 사람은 0왕족이다. 부모의 왕족 점수를 각각 2로 나누어 더한 값이 자식의 왕족 점수가 되고, 왕위를 계승받기를 주장하는 사람들 중 왕족 점수가 가장 높은 사람을 출력하면 되는 문제이다. 💡첫번째 아이디어 예제 입력 9 2 edwardi charlesi edwardi diana philip charlesi mistress wilhelm mary philip matthew wilhelm helen edwardii charlesi laura alice laura charlesi helen alice bernard henrii edwardii roxane charlesii elizabeth henrii charlesii matthew 예제 입력1..

🤔문제 이해 0이 맨 앞에 올 수 있으므로 1~N자리의 숫자 중 i번째 숫자가 i+1번째 숫자보다 작거나 같은 수의 개수를 구하는 문제이다. 💡첫번째 아이디어 일단 맨 처음에 0이 오고 그 다음에 올 수 있는 숫자들을 나열해 봤다. N이 커질수록 중복되는 값들이 보였고 DP 문제임을 확신했다! 🔥풀이🔥 dp[i][j]에서 i는 맨 처음에 올 수 있는 수로 0~9까지를 나타내고, j는 자릿수를 의미한다. 자릿수가 j일 때 dp[0][j]는 dp[0][j-1] ~ dp[9][j-1]까지의 값을 다 더한 값이다. 구하고자 하는 자릿수까지 dp를 채웠으면 마지막으로 그 자릿수로 만들어지는 처음 숫자가 0~9까지인 숫자들의 개수를 다 더한다. 모든 dp연산과 마지막 총합, 출력까지 %10007 연산을 해주어 계산..