다익스트라 알고리즘의 활용 문제 처음에는 각 면접장마다 다익스트라를 K번 돌리려고 생각했었는데, 이 경우에는 면접장의 개수가 많기 때문에 TLE를 받게 된다. 다익스트라를 한번만 돌리되 처음에 넣는 노드를 K개 넣어주어야 한다. 모든 면접장과 거리 0으로 연결되는 가상의 도시를 하나 만든다고 생각해도 무난하다. 다익스트라를 돌리고 난 뒤의 거리는 각 도시에서 가장 가까운 면접장으로 가는 거리값과 같으므로 이 거리 배열을 순회하면서 최대값을 구해주면 AC를 받을 수 있다. 이때 주의해야 할 점은 탐색방향이 반대가 되므로 방향그래프의 방향도 모두 뒤집어줘야한다는점? 이거때문에 좀 고생좀했습니다. 그리고 범위가 int범위를 넘어갈수있으니 long long 형을 사용해주도록 하자. #include #define..

아니 이게 왜 뇌절 오열 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 처음에 그냥 문자열 길이 긴순으로 적당히 나눠보려했는데 aaaaaaaa 뭐 이런 테스트케이스보고 안될거같다고 깨달아버림 dp[k] 를 k-1번째 인덱스까지 문자열을 A에 포함되는 문자열로 만들수 있는지 여부로 정합시다. 그럼 다음 A.length() 개 문자가 서로 똑같을때 dp[k+A.length()] = 1 로 만들어 줄 수 있겠지요 이 과정을 반..

백준 재활 겸 KOI 준비 겸 라이(kks227)님의 알고리즘 강의를 밀고 있다. 그리디 밀면서 오늘 푼 G5. https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 일단 입력을 보고 센서 좌표가 일직선으로 안들어와서 정렬부터 해줬다. 정렬 하고 보니 테스트케이스에서 3과 6 사이에 연결이 없어야 정답이 나오겠다는 생각이 들었다. 왜 3과 6 사이로 직관했나 생각해보니 3과 6사이의 간격이 가장 커서 뺐다는 결론에 도달했고 ..

https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 이 역시 O(N^2) 문제다 디피 짤때 -1을 INF로 따로 처리한다는게 좀귀찮았다. chtoin map은 글씨를 임의 인덱스로 변환시키고 intoch array는 인덱스를 글씨로 변화시킨다 (k+2)%3을 해준 이유는 (k-1)%3과 동일한 역할을 하면서 C언어에서 음수에 %연산할때 생기는 오류를 막기 위해서이다. inf는 편의상 0x3f3f3f3f = 1061109567으로 했다. 사실 잘 안쓰는데 memset하려니 귀찮아서 이번엔 이걸로 해봤다. dp..

N이 그리 크지 않아서 O(N^2) 풀이를 적용할 수 있다. https://www.acmicpc.net/problem/22971 22971번: 증가하는 부분 수열의 개수 길이가 $N$인 수열 $A$가 주어진다. 수열의 $i$번째 원소($A_i$)로 끝나는 증가하는 부분 수열의 개수를 출력하는 프로그램을 작성하자. 단, 수가 너무 커질 수 있으니 $998\,244\,353$으로 나눈 나머지를 www.acmicpc.net 심지어 문제에서 친절하게 점화식 짜는거까지 도와준다 dp[i]를 Ai로 끝나는 증가하는 부분 수열의 개수로 정의하면 dp[i]를 1로 초기화 해두고, (0 A[i]; } for(int i=1; i

[원석방 산하 폐수방] 1일차 셋 div 2 B번. 뇌절오지게했다. 이놈의다익스트라 구현만 1e9번 했는데 아직도 못외웠다는점에서 코더가 멍청하다는걸 바로알수있다... :blobsob: https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 보고 다익스트라는 빠르게 떠올랐었다. 야쿠르트 아줌마 경로구하는것도 그냥 다익스트라를 많이 돌려주면 해결된다. 쬐끔 까다로웠던 부분이 야쿠르..