문제 링크 1. 문제 풀이 주어진 햄버거를 적절하게 분배하여 길원이가 선배들보다 효용이 높지 않으면서 최대 효용을 얻어야 하는 문제다. 먼저 주어진 햄버거의 효용의 합을 구해 변수로 저장한다. 이후 2차원 방문 체크 배열을 활용해 행 인덱스와 열 인덱스가 각각 선배들이 먹은 햄버거의 효용의 합이 되게 하면 방문 체크 시 길원이가 먹은 햄버거의 ...

문제 링크 1. 문제 풀이 주어진 막대를 이어 붙이는 것이 가능할 때 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 문제다. $N$ 이 꽤 작긴하지만 각 변에 어떤 막대를 배치할지 찾는 단순한 완전탐색으로는 $O(5^N)$ 이라서 어렵다.(네 변 + 안 고르기로 총 5가지 선택지) 해당 문제는 4차원 dp를 활용해서 직사각형의 왼쪽 변은 $...

문제 링크 1. 문제 풀이 $1$ 부터 $N$ 까지 각 수의 배수 번째 창문의 상태를 바꿀 경우 열린 창문의 개수를 구하는 문제로 임의의 $M$ 번 창문에 대해 해당 창문을 열거나 닫을 수 있는 수는 $M$ 의 약수들만 가능하다. 처음에 모든 창문이 닫혀 있으므로 창문이 열려있으려면 약수의 개수가 홀수이면 되며 약수의 개수가 홀수인수는 $1$,...

문제 링크 문제 설명 코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다. 예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다. 종류 이름 ...

문제 링크 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 ...

문제 링크 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들...

문제 링크 1. 문제 풀이 회사에 들어온 사람은 "enter", 회사에서 나간 사람은 "leave" 로 주어지는 문제로 회사에 들어왔으면 집합에 넣고, 회사에서 나갔으면 집합에서 제거해주면 된다. 회사에 있는 사람의 이름을 사전 순의 역순으로 출력해야 해서 트리셋을 집합으로 활용했고 역순으로 설정해줬다. 2. 코드 1. 트리를 사용한 집...

문제 링크 1. 문제 풀이 정수 $n$ 이 최대 $4 \times 10^9$ 일 때, $n$ 보다 크거나 같은 가장 작은 소수를 찾는 문제로 $n$ 이 소수가 아니면 $n + 1$ 을 한 후 소수인지 판정하는 과정을 반복하는 브루트 포스로 찾아나가면 해결할 수 있다. 이때 $n$ 의 제곱근까지만 나누어보는 것으로 소수를 판정하는 계산량을 줄일 ...

문제 링크 1. 문제 풀이 번호가 $1$ 인 포켓몬부터 이름이 주어진 후, 번호가 입력으로 들어오면 포켓몬의 이름을, 이름이 입력으로 들어오면 포켓몬의 번호를 출력하는 문제로 해시맵을 활용하면 간단하게 해결할 수 있다. 포켓몬의 이름은 모두 영어로 되어 있으므로 해시맵에 포켓몬의 이름을 키로, 포켓몬의 번호를 값으로 한 쌍 저장하고, 포켓몬의...

문제 링크 1. 문제 풀이 $6$ 이 적어도 3개 이상 연속으로 포함된 숫자들에 대해 크기 순으로 $N$ 번째 수를 구하는 문제로 $N$ 이 최대 $10,000$ 이라서 브루트 포스로 해결할 수 있다. $665$ 보다 작은 숫자는 어차피 종말의 수가 될 수 없으니 $666$ 부터 종말의 수인지 $1$ 씩 증가시켜보며 $N$ 번째 종말의 수를 찾...