백준3 [백준 19648번 문제] 미하일 2마리 문제 설명위의 그림처럼 된 방향 그래프가 있다. 여기서 미하일이란 캐릭터가 파란색 지점에 총 2마리 놓여있다.1초마다 각 미하일은 인접 노드로 움직인다. 하지만 두 미하일은 각각의 위치에서 반대 미하일까지의 거리가 3이하가 되는 경로쌍으로는 이동하지 않게 되어있다.이런 조건으로 N초가 흘렀을 때 미하일들이 사냥할 수 있는 경로의 총 방법 수를 구해라. 단 두 미하일이 a, b에 있는 경우와 b, a에 있는 경우는 다른 경우로 취급한다.입력10억 이하의 정수출력n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지과정입력값의 시간초가 10억이다. 얼핏보면 시간제한이 7초이기 때문에 풀 수 있을 것처럼 느껴지기도 하지만 사실 10억 초에 순간마다 100번만 계산을 해도 총 계산은 1.. 2024. 5. 30. [백준 27652번 문제] AB 문제설명집합 두개가 있고 3가지 커맨드가 있음add,delete,find,add, delete는 더하고 지우기 가 끝find는 문자열을 둘로 나눠서 앞의 부분은 A 뒷부분은 B에서 찾을 수 있는 경우의 수의 총합을 찾아서 출력하는 함수다.입력첫째 줄에 쿼리의 개수 Qn줄동안add A aba delete A a find abab출력find 구문마다 나올 수 있는 경우의 수의 총합을 출력과정처음에는 이렇게 생각했다 일단 find쿼리에서 일어나는 일은 O(문자열길이) 안에 끝내야한다고 생각한다. 애초에 집합으로 저장해야한다고 하기도 했고 해시가 바로떠오른다. 저장되는 쿼리 양도 해봤자 1000이다.유일하게 걱정되는건 subStr이 O(글자수)라고 알고있는데 1000 글자라면어찌됐던 1000 * 1000 번 연.. 2024. 5. 9. 백준 9527번 1의 개수 세기 문제풀이 입력 두 자연수 A, B (1 ≤ 10^16) 입력범위가 굉장히 넓다. 전체적인 범위에서 어떤 수를 이진수로 바꾸고 그 차이에 대해서 바깥의 1을 컨테이너라고 지정하고 그게 그 모든 경우의수가 쉽게말해서 16부터 31 사이의 수라면 바깥 1은 15번 등장하고 나머지는 모든 경우의 수의 절반 말그대로 888 등장할것임 출력 어떤 두 수 사이의 수들에 대해서 1이 등장하는 횟수를 출력해라. 과정 입력값이 10 ^ 16까지기 때문에 모든 수를 늘려가면서 세는것은 엄두도 못 낼 일 다만 직관적으로 이해하기 쉬운건 1이 등장하는데 패턴이 있을 것이라는 점이다. 예를들어 0000(2)부터 1111(2)까지 1이 등장하는 횟수는 당연히 32회다.중복 순열의 총 경우의수에 각각의 자리수가 등장할 확률은 1/2를 곱하면.. 2024. 3. 22. 이전 1 다음
