알고리즘/수학5 [백준 16565] N포커 / 자바 / 수학(포함배제원리 + 모듈러 연산) #문제 레벨: G1알고리즘: 수학(포함배제원리 + 모듈러 연산) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16565#문제 풀이 쌍이 맞는 조합 카드 4개를 뽑고 나서 나머지 카드를 뽑으면 된다. 쌍이 맞는 4개의 카드를 뽑는 경우의 수는 13이고 나머지 카드를 뽑는 건 52-4= 48에서 N-4를 뽑으면 되니48C(N-4)를 해주면된다. 13x 48C(N-4)위는 틀렸다.위 공식은 두 개 이상의 포카드가 있는 경우를 중복 계산할 수 있다. 예를 들면 N=8일 때 K 조합을 뽑고 48C4에서 포카드 조합이 나오거나 안 나오거나 두 케이스를 커버칠 수 있는 거 아니야? 라고 생각할 수 있다. 그 생각이 맞다. 그러나 우리는 중복.. 2024. 9. 23. [백준 12850] 본대 산책2 / 자바 / 수학 #문제 레벨: G1알고리즘: 수학풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/12850#문제 풀이 N의 최대값이 1억이다. 이미 브루트포스는 실패이다. 그렇다 하면 종료조건을 걸얼 백트래킹하게 하는 건 어떨까? 백트래킹의 조건은 학생회관까지 갔는데 남은 시간이 3분인 거다. 돌아가는 시간은 최소 4분이 걸리기 때문에 이미 실패다. 이 뒤에 상황을 안 살펴봐도 되는 거다.아니다. 그렇다 하더라도 무조건 시간복잡도에서 걸릴 것이다. 생각이 나지 않는다. 그래서 다른 사람의 풀이를 참조하였다. 문제의 포인트는 행렬곱셈이다. 예를 들어 설명하겠다. 아래 표는 1초에 i에서 j까지 갈 수 있는 경우의 수 배열이다.N =1ABCA011B.. 2024. 9. 12. [백준 2166] 다각형의 면적 / 자바 / 수학(신발끈 공식) #문제 레벨: G5알고리즘: 수학(신발끈 공식)풀이시간: 10분힌트 참조 유무: 유https://www.acmicpc.net/problem/2166#문제 풀이 신발끈 공식고등학생 때 배웠던 것 같은데 까먹었다. 아닌가 중학교 때 배웟나. 어찌 됐든 도형의 넒이 구하는 공식은 기억하는게 좋을 것 같아 따로 남겨놓는다.신발끈 공식은 간단하다. 빨간색으로 이어진 숫자끼리 곱하고 다른 빨간색선들이랑 더해준다. 파란색도 마찬가지로 파란색끼리 합쳐준다. 그리고 Math.abs(빨간색 총합 - 파란색 총합) /2 해주면 도형의 넓이가 나온다. #풀이 코드 import java.io.*;import java.util.*;public class Main { public sta.. 2024. 9. 1. [백준 11401] 이항 계수3 / 자바 / 수학(파스칼 + 모듈러) #문제 레벨: G1알고리즘: 수학(파스칼 + 모듈러풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/11401#문제 풀이 이항 개수란 N개에서 순서상관없이 K개를 뽑는 것을 말한다. 보다시피 조합문제는 파스칼 문제로 치환된다. 그런데 N의 숫자가 상당하다 이정도의 파스칼을 구했다가는 어떠한 변수에도 담을 수 없다.(알고리즘 문제를 풀 때 12팩토리얼과 20팩토리얼은 각각 int와 long형이 넘어간다는 것을 알면 좋다.) 그래서 우리는 이 문제를 풀기위해서 크게 두가지를 구현해야 한다. 1. 파스칼 수 구하는 법2. 모듈러 연산(변수에 담기 위해) 1. 파스칼 수 구하는 법//일반 파스칼main { print(factorial.. 2024. 8. 9. [백준 1016] 제곱 ㄴㄴ 수 / 자바 / 수학(에라토스테네스의 체) #문제 레벨: G1알고리즘: 수학(에라토스테네스의 체)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1016 #문제 풀이 에라토스테네스의 체 문제를 한 번이라도 풀어본 사람이라면 이 문제를 보자마자 그 문제라는 것을 직감할 것이다. 다른 방식으로 찾게 된다면, 시간복잡도에서 걸리기 때문입니다. 체에서 알 수 있듯이 에라토스테네스의 체는 제한 숫자내에서 2,3,...의 제곱들을 미리 걸러주는 것는 것입니다. 만약 4의 차례가 왔다면 앞서 2의 제곱으로 이미 걸러졌기 때문에 4는 탐색을 안 하고 패스되는 것입니다.이 문제는 소수를 찾는 것이 아니고 어떤 숫자의 제곱으로 나눠지나 안 나눠지나 판단하는 에라토스테네스체의 응용문제입니다.#풀.. 2024. 8. 8. 이전 1 다음
