너와 나의 스토리

문제: https://www.acmicpc.net/problem/1018 문제풀이:8*8로 짤랐을 때 수정해야할 부분이 최소인 체스판의 수정할 칸의 개수 구하기 - 검은색과 흰색을 번갈아 칠한 판을 미리 만들어 둠 * 검은색으로 시작하는 판의 반대는 흰색으로 시작하는 판이므로 하나만 만들면 됨 - 8*8로 자를 수 있는 모든 경우를 본다- 검은색으로 시작하는 판과 흰색으로 시작하는 판 각각 따로 비교해준다 * 처음에 예제1번이 맞는 모양인 줄 알고 왜 답이 1인가 했는데 가운데가 틀렸었음 ㅎㅎ 소스코드:https://gist.github.com/hovy1994/36e530e127bd04c3ace161622e313e6e#file-1018

문제: https://www.acmicpc.net/problem/1107 문제풀이: case1) 100번에서 +로 이동하는 경우, -로 이동하는 경우 -> result=abs(100-num);case2) num에서 ( + or - )로 이동해서 가능한 숫자까지의 거리 -> 도달한 가능한 숫자의 길이 더해줘야함 * 예외처리- 길이를 구할 때 while (tmp > 0) {len++;tmp /= 10;} 이런식으로 구했는데 tmp=0인 경우는 길이가 1이여야하는데 저 코드만 쓰면 길이가 0으로 처리됨 즉, if(tmp==0) len=0; 필요 소스코드:https://gist.github.com/hovy1994/36e530e127bd04c3ace161622e313e6e#file-1107

문제 : https://www.acmicpc.net/problem/7453 * 혼자서 못 품 ㅠㅅㅠ 다른 사람 블로그 보고 이해했다. 문제 풀이:- n이 최대 4000이므로 단순하게 포문을 이용해 다 계산하면 시간 초과가 난다- a, b, c, d를 한번에 계산해서 합이 0인지 판단하는 것이 아니라 가능한 (a, b), (c, d)쌍의 값을 각각 모두 더하고 각 쌍의 합이 0인 것들의 개수가 답이 된다. for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {v.push_back(arr[i][2] + arr[j][3]); // (c,d)의 합 모두 구하기}} * 처음에는 o . . o . o 꼴로만 구할 수 있고 o . 이런꼴은 못 구하는거 아닌가라는 생각..

문제: https://www.acmicpc.net/problem/9205 문제 풀이: - 처음에 플로이드 와샬로 풀었는데 틀렸다. 틀린 이유를 모르겠어서 그냥 bfs로 풀었다 ㅎㅎ - 거리가 1000이하로 차이 나는 곳들 다 queue에 넣다가 락 페스티벌까지 도달 했으면 check=true; 그렇지 않고 끝나버렸으면 "sad" 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-9205

문제: https://www.acmicpc.net/problem/13168 문제풀이: - map 이용해서 각 대중교통이름을 정수로 나타냄- 가야할 곳들 순서대로 vector에 삽입- 비용은 내일로 티켓 사용할 때와 사용하지 않을 때를 따로 저장. a->b 로 갈 수 있는 대중교통이 여러개이면 가장 작은 값으로 저장. (참고로 양방향) - 정해진 루트를 vector에 넣어둔 순서대로 dist 더해줌 // 그냥 순서대로 sum+=dist[v[0]][v[1]]; ~~~ 해주면 됨 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-13168

문제: https://www.acmicpc.net/problem/1956 문제 풀이: - 플로이드 와샬 알고리즘 사용- 자기 자신으로 가는 (dist[a][a]=INF) 거리도 INF로 초기화- 자기 자신으로 가는 거리가 INF가 아니면 사이클이 존재하는 것 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1956

문제: https://www.acmicpc.net/problem/2610 문제 풀이: - 플로이드 와샬 알고리즘 이용해서 dist 구하기 - bool check[101] 배열 이용해서 연결된 그룹 구분하여 vector에 저장 - 그룹별로 "의사전달시간 중 최댓값이 최소가 되도록" 대표 선정 (이거 이해 잘못해서 틀림 ㅎ) ㄴ 의사전달시간을 각 사람별로 다 더하는 것이 아니라 대표로부터 가장 멀리 떨어진 사람 (다른 사람을 가장 많이 거쳐야 하는 사람) 과의 거리 -> 의사전달시간 중 최댓값 가 최소인 사람을 대표로 선정 - 대표들을 vector에 저장해서 sort한 다음 작은 번호부터 출력 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa65993..

문제: https://www.acmicpc.net/problem/1613 문제 풀이: - 플로이드 와샬 알고리즘 이용 - 단방향이므로if( dist[a][b]!=INF ) -> a가 b보다 앞선 사건 (a->b로의 경로가 존재) else if( dist[b][a]!=INF ) -> b가 a보다 앞선 사건 (a->b로의 경로는 존재하지 않지만 b->a로의 경로는 존재) else -> 알 수 없음 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1613