목록수학 (34)

1일1알

백준 5747 Odd or Even C++

게임 규칙 : 두 사람이 동시에 0~5의 손가락을 내밀어서 두 손가락의 합이 짝수이면 Mary의 승리, 홀수이면 John의 승리이다. Mary는 파란색 카드에, John은 빨간색 카드에 자신이 내민 손가락의 정보를 기록하였다. 현재 상황 : 테스트케이스 만큼의 게임을 마치고 카드 더미들을 떨어트렸다. 카드의 색이 달라서 색을 보고 누구의 기록인지 알 수 있지만, 순서는 알 수 없다. 이 때, Mary가 확실히 이긴 최소의 게임 수를 구해야 한다. 각 테스트 케이스의 첫 줄은 Mary의 카드이고, 두번째 줄은 John의 카드이다. Mary의 카드를 보면서 짝수이면 John의 카드에서 홀수를 골르고, 홀수이면 짝수를 골라서 Mary가 최대한 많이 지게 한 뒤, 테스트 케이스에서 진 횟수를 빼면 확실히 이긴 ..
알고리즘 2022. 1. 23. 11:29
백준 16943번 숫자 재배치 C++

a에 있는 숫자들을 백트래킹을 이용하여 새로운 숫자를 만들고, b보다 작은 값들 중 가장 큰 값을 구했다. 처음 시작이 0인 숫자는 제외하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; string a; int b; int ans = -1; vector nums; vector visited(11, false); void BT(int len, int num) { if (len >= nums.size()) { if (num < b) { ans = max(ans, nu..
알고리즘 2022. 1. 17. 09:49
백준 16922번 로마 숫자 만들기 C++

백트래킹을 이용하여 가능한 모든 경우를 구해서 나온 값을 set에 넣는데, 문자의 순서는 상관 없기 때문에 중복을 피하도록 구현했다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; int values[4] = { 1,5,10,50 }; unordered_set s; void BT(int idx, int cnt, int sum) { if (cnt >= n) { s.insert(sum); return; } for (int i = idx; i < 4; i++) ..
알고리즘 2022. 1. 16. 13:02
백준 1500 최대 곱 C++

처음에 백트래킹으로 해결하려다가 시간초과가 났다. 곱하는 수들의 차이가 적을수록 곱이 커지기 때문에 그것을 이용해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll s, k; ll ans = -1; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> s >> k; ll a = s / k; ll b = s % k; ll ans = 1; for (in..
알고리즘 2021. 12. 27. 12:42
백준 1052번 물병 C++

우선 n1일 동안 n에서 n을 넘지 않는 최대의 2의 제곱을 빼가면서 n을 줄였다. 물론 k도 1씩 줄여줬다. 빼는 도중에 혹은 while문을 빠져나왔을 때 n이 0이라면 물병을 더 구매할 필요가 없기 때문에 0을 출력하고 프로그램을 종료하였다. n가 0이 아닌 경우에는 n보다 큰 2의 제곱 중 가작 작은 수에서 n을 빼면 구매해야하는 물병의 최솟값이다. 출력 조건에 정답이 없을 경우에는 -1을 출력하라고 했는데, 정답이 없을 경우는 없을 것 같아서 만들지 않았는데 통과되었다. 속임수였던 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include..
알고리즘 2021. 12. 25. 10:59
백준 1790번 수 이어 쓰기 2 C++

분명히 답은 맞고 전혀 오래 걸릴 코드가 아닌데 계속 시간초과가 나서 고민을 많이 했는데 알고보니 while문 안의 tmp를 int형으로 선언해서 while문을 빠져나오지 못해 시간초과가 났다. 풀고나니 허무했다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll n, k; cin >> n >> k; ll len = 0; ll c..
알고리즘 2021. 12. 24. 14:24
이전 Prev 1 2 3 4 5 6 Next 다음