승코딩당당당

문제[C++] 백준 9375: 패션왕 신해빈 SILVER 3https://www.acmicpc.net/problem/9375 접근 방법이 문제는 옷의 이름은 필요 없고, 종류(type)별로 몇 개 있는지만 알면 되는 경우의 수 문제다.입력으로 (옷 이름, 옷 종류)가 들어오지만, 실제로 필요한 건 “종류별 개수”이기 때문에map을 사용해서 아래와 같이 저장했다.key : 옷의 종류value: 그 종류에 속하는 옷의 개수예를 들어, 아래와 같다면 각 종류별 선택지는 다음과 같다.headgear 2개eyewear 1개headgear: (안 씀) + 2개 중 하나 = 3가지eyewear: (안 씀) + 1개 중 하나 = 2가지따라서, 전체 경우의 수는 3 * 2 = 6이 된다.이를 일반화하면, 각 종류마다 ..

문제[C++] 백준 17219: 비밀번호 찾기 SILVER 4https://www.acmicpc.net/problem/17219 접근 방법이 문제는 사이트 주소가 주어졌을 때 해당 비밀번호를 빠르게 찾아 출력하는 문제다.핵심은 “탐색 속도”다. 처음에는 vector에 (사이트, 비밀번호) 쌍을 저장해 두고, 질문이 들어올 때마다 처음부터 끝까지 순회하며 찾는 방식으로 구현했다.하지만 이 방식은 매 질의마다 선형 탐색(O(N))이 필요해서, 입력 크기가 커지면 결국 시간 초과가 발생한다. 그래서 접근 방식을 바꿔, 키를 기준으로 바로 값을 찾을 수 있는 자료구조를 사용해야겠다고 판단했다.여기서 사용한 것이 바로 map이다. map을 사용한 풀이 아이디어map은key → value 형태로 데이터를 저장하고..

문제[C++] 백준 1456: 거의 소수 GOLD 5https://www.acmicpc.net/problem/1456 접근 방법이 문제는 구간 [A, B] 안에 있는 거의 소수(= 어떤 소수 p에 대해 p², p³, p⁴ … 꼴인 수)의 개수를 세는 문제다.모든 수를 일일이 나눠보면 범위가 너무 커서 불가능하므로, "소수의 거듭제곱을 만들어서 세는 방식”으로 접근한다. 1. √B 까지의 소수 먼저 구하기어떤 거의 소수 p^k가 B 이하라면, 밑이 되는 소수 p는 반드시 p ≤ √B를 만족한다.그래서 먼저 2 ~ √B 범위에 대해 에라토스테네스의 체로 소수를 구한다.vector vect;for (LL i = 0; i 2. 각 소수 p에 대해 p², p³, p⁴… 생성해서 카운트i가 소수라면 i^2부터 ..