정화 코딩

https://www.acmicpc.net/problem/23817 이 문제 풀 때 고수들이 옆에 있었어서 그들이 걍 다 해줌. 저는 풀이를 듣고 음 그렇구나. 천재다. 구현해볼게. 했음다. 첫번째 풀이. vst 배열: 현재 위치 (i, j) + 어느어느식당 방문했는지 (길이가 20인 비트스트링) 길이가 20인 비트스트링 → 2^20 하면 너무 큼 → 근데 어차피 최대가 5개 켜지는 거임 → 2^20 중에 안 쓰는 게 너무 많음 (어떤 걸 안 쓰는지 모름) → map 이용 vector>> → 최단 거리를 두번째 int에 저장하는 셈 vector>> (= vector>>) → 방문 했는지 안 했는지를 bool에 저장하는 셈 근데 이렇게 하면 터짐...  두번째 풀이.모든 식당과 식당 (+시작점) 사이의 거..

https://www.acmicpc.net/problem/13172 이 문제의 핵심을 정리하면 아래와 같다. 기약분수 a/b를 다음과 같이 하나의 정수로 표현할 수 있다.  이 때 X는 1,000,000,007과 같은 큰 소수이다.b^(-1)은 b의 모듈러 곱셈에 대한 역원인데, 다음과 같이 계산할 수 있다.  이 정도만 알면 문제를 풀 수 있다. 이제 구체적으로 어떻게 구현할지 생각해보자.한 줄에 분모와 분자 순서대로 한 쌍의 분수가 들어온다. 각 분수에 대해 a * b^(-1) mod X 를 구하면 된다. 그리고 모든 값들을 마치 확률을 더하듯 그냥 더해주면 된다.  내가 헷갈렸던 점은 기약분수 a/b에 대해서 저렇게 계산해야 된다고 하길래 들어온 분모와 분자에 대해서 우선 기약분수 형태로 만들어줘야..