본문 바로가기

수학4

[백준 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.
[백준 13458] 시험감독 / 자바 /그리드 문제         레벨: B2알고리즘: 구현 풀이시간: 10분힌트 참조 유무: 무https://www.acmicpc.net/problem/134581 번째 시도   삼성SW역량테스트인데도 말도 안되게 쉬워 푸는 내내 경계했다. 그러나 쉬운 문제가 맞았다. 단 주의해야 하는 건 입력값이다. 입력값의 최대값을 생각해보자.B =1, C= 1, 시험장의 개수 1,000,000 x 응시자수 1,000,000  = 1,000,000,000,000 1조이기 때문에 ans를 int형으로 쓰면 틀린다.import java.io.BufferedReader;import java.io.InputStreamReader;class Main { public static void main(String[] args) throw.. 2024. 7. 3.

티스토리툴바