14172 Moocast (G5) 모든 소들의 쌍에 대해서 a->b로 가는 거리가 power 안에 들어오면 간선으로 이어준다. 거리를 계산할때 제곱끼리 비교해서 실수 연산을 최대한 피해준다. 그리고 모든 점에 대해서 BFS로 도달할 수 있는 소들의 최댓값을 구해주면 된다. http://boj.kr/a841ac2eadbe418ba6030ddad02d28e9 14464 소가 길을 건너간 이유 4 (G1) 소들을 Bj를 기준으로, Bj가 같다면 Aj를 기준으로 정렬한다. 닭은 Ti를 기준으로 오름차순 정렬한다. 그리고 소들을 한 마리씩 보면서 그리디하게 Ti가 가장 작은 닭에게 매칭시켜주면 된다. http://boj.kr/e5b7f5e2de2f400e874a91d1cd9820d0 2109 순회강연 (G3)..
3013 부분 수열의 중앙값 (G3) 주어진 수열에서 중앙값이 B인 부분 수열의 개수를 계산해야한다. B의 위치를 기준으로 이전의 원소들을 보면서 psum을 B보다 크면 +1, B보다 작으면 -1해주면서 map에 특정 누적합 발생 빈도를 기록한다. 그리고 B의 위치부터 오른쪽으로 보면서 다시 psum을 계산하면서 -psum이 왼쪽 부분에서 발생했는지 확인해서 해당 부분 수열의 개수를 답에 세주면 된다. http://boj.kr/96cf2289845049e38029a2fbfe662fd5 1865 웜홀 (G3) 벨만 포드 알고리즘을 적용하여 음의 사이클이 존재하는지 여부를 판단하는 고전적인 문제이다. 그래프의 컴포넌트가 하나가 아닐 수도 있으므로 편의상 가상의 정점 0을 추가하여 실제 모든 정점을 이어줬다..
15927 회문은 회문아니야!! (G5) 문자열 s가 주어졌을때 길이를 n이라고 하자. s 자체가 팰린드롬이 아니라면 n을 출력해주면 된다. s가 팰린드롬이라면 만약에 전체가 똑같은 글자로 이루어진 팰린드롬이면 모든 부분문자열이 팰린드롬이므로 -1이 답이다. 그렇지 않다면 맨 앞이나 뒤에서 하나만 빼주면 팰린드롬이 아니게 된다. 즉 n-1이 답이다. http://boj.kr/3cb717aee0e141adb4e5edd5b5b46afb 14370 전화번호 수수께끼 (Large) (G4) 각 숫자에 대응하는 영어 단어에서 고유한 문자를 찾는다. 0 : ZERO (Z)2 : TWO (W)4 : FOUR (U)6 : SIX (X)8 : EIGHT (G)1 : ONE (O) - O는 0에서 쓰였으므로 0을 먼저 ..
15961 회전 초밥 (G4) 슬라이딩 윈도우로 고정된 구간을 연속적으로 보면서 초밥 가짓수의 최댓값을 구한다. 쿠폰 사용 여부를 따로 변수로 둬서 누적해서 세는 경우가 없도록 했다. http://boj.kr/07bfe0b8abf94fc99b0e67dd9e6f4a22 9011 순서 (G5) R를 이용해서 S를 구하려면 R의 뒤에서부터 거꾸로 봐야지 원소들을 하나로 정할 수 있다. check 배열을 따로 둬서 현재 위치의 앞에 r[i]가 check 안되어있으면 s[i]를 정할 수 있다. 끝까지 봤는데도 아직 자리를 못찾으면 IMPOSSIBLE를 출력해준다. http://boj.kr/c3d6b307fa5640e49d4b74a223c3f1cf 16985 Maaaaaaaaaze (G2) 판 하나당 4가지 경..
9470 Strahler 순서 (G3) 위상 정렬을 하면 되는데 조건이 붙어있다. 노드로 들어오는 강의 순서 중 가장 큰 값을 cnt 배열을 두고 관리했다. 이 부분에서 구현이 조금 엉켜서 애먹었다. http://boj.kr/bd1acde263c04d71bcdb47d6187cbce5 15483 최소 편집 (G3) d[i][j] = 문자열 a의 첫 i개의 문자를 문자열 b의 첫 j개의 문자로 만드는데 필요한 최소 편집 횟수 만약 a의 i번째 문자와 b의 j번째 문자가 같다면 d[i][j] = d[i-1][j-1]이다. 문자가 다르다면 삽입, 삭제, 교체 세 가지 경우 중에서 최소값을 선택해서 테이블을 채운다. http://boj.kr/c148fea9541c466d821362fc4404ad81 2655 ..
2623 음악프로그램 (G3) 각 PD들의 가수 출연 순서에 따라 단방향 그래프를 만든다. 그 다음에 Topological Sort를 해줘서 전체 출연 순서를 정한다. Directed Acyclic Graph를 이루면 전체 가수의 수만큼 정확히 출력이 될것이고 아니면 순서 정하는 것이 불가능하므로 0을 출력한다. http://boj.kr/09f1e0b6e82c457e89e3a05fb6143178 4386 별자리 만들기 (G3) 각 별들의 좌표를 정점으로 생각하고 좌표들 간의 거리를 간선으로 생각하면 그래프를 구성할 수 있다. 그리고 Minimum Spanning Tree를 구성하면 별자리를 만드는 최소 비용을 구할 수 있다. http://boj.kr/a587be0a5a53456583384ae27fbc0..
8/22 Problem Solving
2825 수업시간에 교수님 몰래 교실을 나간 상근이 (G2) 비트 마스크로 0~9 사이의 숫자가 포함되어 있는지 여부를 상태로 표현해서 세준다. 쌍의 개수를 세줄 때 자기자신끼리의 쌍과 중복되는 쌍은 제거해야한다. http://boj.kr/065bfe2aa12a4a85abb60aed0ed3d74a 17497 계산기 (G2) 처음에는 BFS로 생각했는데 경우의 수가 최대 4^99가 되서 불가능하다. 연산이 전부 2와 연관이 있는것에 주목하자. 2를 더하는 것은 1번째 비트에 1를 추가하는 것과 같고 빼는 것도 마찬가지이다. 곱하기는 left shift, 나누기는 right shift와 같다. 우리가 구해야 하는 것은 0에서 N까지 가는 방법인데 N에서 0으로 만드는 방법을 생각해보자. 1. 0번째 비트에..
오늘부터 연말까지 골드 문제 중에 랜덤으로 최소 5문제 이상씩 풀어보려고 한다. 골랜디가 80% 이상 방어되는게 목표다. 꾸준히 해보자.. 1477 휴게소 세우기 (G4) 처음에는 priority queue를 이용해서 greedy하게 m번에 걸쳐서 제일 큰 구간을 반씩 자르면 될것이라고 생각했다. 근데 생각해보니까 한 구간을 여러번 분할하는게 답이 되는 경우도 있어서 이 접근은 틀렸다. 구간의 최댓값의 최솟값이 될 수 있는 범위를 후보로 놓고 parametric search를 해서 답을 찾으면 된다. http://boj.kr/4481a6d19d05480db5e86a48da136770 2473 세 용액 (G3) 일단 정렬한 후에 모든 용액에 대해 하나의 용액을 fix하고 나머지 두 개의 용액에 대해서 ..
https://www.acmicpc.net/problem/5573 5573번: 산책 첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107) 둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 www.acmicpc.net d[i][j] = n-1번 산책한 후 교차로 (i,j)의 방문 횟수 i) d[i][j] = 짝수이면 초기 방향 상태가 그대로 유지된다 ii) d[i][j] = 홀수이면 초기 방향 상태와 방향이 다르다 위의 dp 정의를 통해 점화식을 찾아보자. 시작점은 무조건 지나므로 초기값 d[1][1] = n-1이다. 오른쪽, 아래쪽으로 가는 경우인 d[i][j+1],d[i+1]..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net d[x][y] = x번째 행렬부터 y번째 행렬까지 곱했을 때 곱셈 연산의 최소값 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include int n,a[500][2],d[500][500]; int go(int x,int y) { if(d[x][y]) return d[x][y]; if(x==y) ..