수학(5)
-
백준 10974번: 모든 순열 (C++)
https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 골드5 문제 푸는데 구현이 되게 까다로운 문제가 순열로 너무 쉽게 풀리는 것을 보고 현타와서 순열 알고리즘을 몇개 풀었다. next_permutation(v.begin(), v.end()) 을 실행하면 입력받은 배열을 바로 다음 순열로 변경한다. do while을 쓴 이유는 next_permutation(v.begin(), v.end()) 실행 시 배열을 변경시키기 때문이다. 정렬된 배열을 한번 출력하기 위해 사용했다. 전체 코드 #include #include #include u..
2023.01.21 -
백준 11947번: 이런 반전이 (C++)
https://www.acmicpc.net/problem/11947 11947번: 이런 반전이 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 자연수 T가 주어집니다. 다음 T개의 각 줄에는 하나의 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000,000,000) www.acmicpc.net 풀이 처음에 문자열로 1부터 하나씩 계산해보려다가 n이 최대 10억이라서 시간초과가 난다고 생각이 들었다. 그래서 고등학교때 배웠던 함수의 최댓값을 활용했다. 우선, 정수 n을 4자리 수 abcd의 형태로 나타내고 식을 세워보았다. 이렇게 n과 F(n) 을 곱한다고 가정했을 때, 초항이 큰 수가 최댓값이 된다는 것을 알았고 a에 대한 2차원 함수를 그려보니 a가 4.5일 때, 최댓값이 된다. a는 정수이기 ..
2023.01.20 -
백준 2502번: 떡 먹는 호랑이 (C++)
https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 피보나치의 첫번째 항과 두번째 항을 구하는 문제. 먼저, 첫번째 항과 두번째 항만 구하면 되기 때문에 변수를 최대한 줄여 나타냈다. 그리고 첫번째 항과 두번째 항의 상수의 점화식을 도출해서 X[31][2]를 선언, 2차원 배열에 순서대로 저장해주었다. (여기서는 2번째부터 표현했는데 다시보니 첫번째부터 구해도 됐다.) (X1 제일 앞에 1, X2 제일 앞에 0) 변수가 두개가 되기 ..
2023.01.18 -
백준 1111번: IQ Test (C++)
https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 풀어보려고 시도했으나 접근법을 몰라 풀이 방법만 찾아봤다. 그리고 나름대로 다시 분석하여 풀어봤다. 케이스를 나누어서 구하는 방식이었는데 공식을 보니 고등학교때 풀었던 변수의 범위에 따라 케이스를 나누어서 계산하는 문제가 생각났다. 우선 차례대로 식을 쓰면 이런 느낌이다. 그리고 여기서 첫번째 식과 두번째 식을 연립해서 a와 b에 대한 식으로 나타내면 이런식으로 나타낼 수 있다. 이제 N과 X항에 따라 각 케이스를 구할 수 있다. N = 1 , 먼저 X1 밖..
2023.01.18 -
백준 1057번: 토너먼트 (C++)
https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 kim과 im의 번호를 뺏을 때 1이고 그 중 큰 번호가 짝수일 때 둘이 만나는 라운드다. 이 법칙에 따라 while문의 내용을 넣어주었고 kim과 im을 계속 2로 나누어서 진행시켰다. while문을 탈출하면 둘이 만나는 라운드기 때문에 round를 출력시켰다. 간단하게 구성한 줄 알았는데 문제를 풀고 다른 블로그를 찾아보니 조금 더 간단하게 구성한 while문이 있었다. kim을 2로 나눌때 3..
2023.01.17