알고리즘(71)
-
[백준/C++] 9375번 패션왕 신해빈
문제: www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제풀이 해빈이가 입을 수 있는 옷의 경우의 수는 옷의 종류가 상의, 하의, 모자가 있다고 했을때 (상의+1) x (하의+1) x (모자+1) - 1 이다. 여기서 상의, 하의, 모자에 1을 더해준 것은 옷을 입지 않는 경우이고 마지막으로 1을 빼준 것은 해빈이가 세 종류의 옷들 모두 입지 않았을 때를 빼준 것이..
2021.02.16 -
[백준/C++] 2630번 색종이 만들기
문제: www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제풀이 주어진 종이가 같은 색으로 모두 칠해져 있을 때까지 종이를 4 등분한다. 재귀를 이용하여 종이가 같은 색으로 칠해져 있을 때까지 함수를 반복했다. 함수에서 기준점의 인덱스와 종이의 크기를 매개변수로 넘겨주었다. 코드 #include using namespace std; int arr[129][129] = {0}; //종이의 크기는 최대 128x128 int bcnt=0..
2021.02.15 -
[백준/C++] 1676번 팩토리얼 0의 개수
문제: www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제풀이 입력 N에 대하여 N! 이 일의 자리부터 처음 0이 아닌 숫자가 나올 때까지의 0의 개수를 구하는 문제이다. 0의 개수는 N! 를 소인수 분해해서 성분 2와 5의 개수를 구한 다음 둘 중 더 작은 것의 개수를 출력하면 된다. 코드 #include using namespace std; struct tf{ //2와 5의 개수 int two; int five; }; int func2(int num){ //2의 개수 구하기 int cnt2 = 0; while(num%2==0){ num /..
2021.02.13 -
[백준/C++] 1003번 피보나치 함수
문제: www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이 fibonacci(N) 일 때의 0과 1을 각각 몇 번씩 호출하는지를 물어보는 문제이다. fibonacci(N)은 fibonacci(N-2) + fibonacci(N-1) 을 호출하기 때문에 우리가 피보나치 수열을 구할 때 앞의 두 수의 합을 구하듯이 0과 1의 호출 또한 앞선 두 수의 합을 구하면 된다. 이때 N은 40과 작거나 같은 자연수이므로 벡터를 41의 크기로 선언하여 0과 1의 호출 수를 저장하였다. 0 호출 1 호출 fibonacci(0) 0 1 0 fibonacci(1) 1 0..
2021.02.13 -
[백준/C++] 1764번 듣보잡
문제: www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제풀이 이분 탐색 문제이다. 벡터 3개를 선언하여 하나는 듣도 못한 사람, 하나는 보도 못한 사람, 하나는 둘의 중복되는 문자열인 듣도보도 못한 사람을 넣는다. 코드 #include #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin>>N>>M; vect..
2021.02.09 -
[백준/C++] 1620번 나는야 포켓몬 마스터 이다솜
문제: www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제풀이 이분 탐색 문제이다. 포켓몬 이름이 입력으로 들어오면 포켓몬의 번호를, 포켓몬의 번호가 입력으로 들어오면 포켓몬의 이름을 출력해야 한다. 벡터를 두 개 선언해서 하나는 포켓몬 이름을 저장하고 다른 하나는 번호와 이름을 같이 저장한다. 번호와 이름을 같이 저장한 벡터는 sort() 함수를 이용해 사전 순으로 정렬해준다. 문제에 대한 입력을 받을 때 string 형으로 ..
2021.02.06