알고리즘연구소👨💻/백준 (2) 썸네일형 리스트형 [백준 19648번 문제] 미하일 2마리 문제 설명위의 그림처럼 된 방향 그래프가 있다. 여기서 미하일이란 캐릭터가 파란색 지점에 총 2마리 놓여있다.1초마다 각 미하일은 인접 노드로 움직인다. 하지만 두 미하일은 각각의 위치에서 반대 미하일까지의 거리가 3이하가 되는 경로쌍으로는 이동하지 않게 되어있다.이런 조건으로 N초가 흘렀을 때 미하일들이 사냥할 수 있는 경로의 총 방법 수를 구해라. 단 두 미하일이 a, b에 있는 경우와 b, a에 있는 경우는 다른 경우로 취급한다.입력10억 이하의 정수출력n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지과정입력값의 시간초가 10억이다. 얼핏보면 시간제한이 7초이기 때문에 풀 수 있을 것처럼 느껴지기도 하지만 사실 10억 초에 순간마다 100번만 계산을 해도 총 계산은 1.. [백준 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 번 연.. 이전 1 다음
