이렇게 풀어도 레이팅이 오르는 지금 수준;;

A. Two Choices

N개의 M개의 0, 1로 이루어진 문자열이 주어질 때, 정답 문자열과 틀린 개수가 같은 쌍 (i, j) 의 개수

그냥 1의 개수의 홀짝성으로 나눠서 곱해주는 문제. 

B. Plus Matrix

모든 (i, j) 에 대해 Cij = Ai + Bj 가 되도록하는 A와 B가 있으면 출력하여라. 

그냥 가장 작은 row 에 대해서 해주면 됨. 어떻게 풀어도 되는데 그걸 구체화시키기가 좀 짜증나는 문제

C. N Coloring

N 이 입력되었을 때 i가 j의 약수인 경우 Aj != Ai 이도록 하고, 최댓값이 가장 작은 수열 A를 N개 출력하여라

N = 2^p1 * 3^p2 * ... (소수)^pn 일때, N은 최대 p1+p2+...pn+1 이 됨. 그게 걍 최소임. 

그래서 그냥 저걸 값으로 다 해주면 됨. 그러면 깔끔하게 되더라

D. Odd Degree

N개의 노드와 M개의 간선을 가진 그래프가 주어질 때, 이 중 간선 몇 개만을 취해 홀수 Degree인 노드가 K인 것을 만들 것이다. 모든 K에 대해 이 개수를 세라. 

대회땐 못 풀었음..

뭔가 아예 어떻게 풀어야할지 감을 못 잡았던거 같음. 

기존의 홀수에서 뭐 더 붙이는 형식으로 생각을 해봤었는데 아니었다

정해는 트리에서 그래프로 확장해나가는 풀이인데.. 트리일때 홀수 Degree 노드가 K인 것은 nCk 라고 함 (k가 짝수일때만). 그냥 홀수 Degree가 될 k개를 정해주기만 하면 트리에서는 그것을 2개씩 짝지어서 연결하는 것만으로도 가능하고, 그것이 유일하다고 함. 

그래프에서는 스패닝 트리를 임의로 한 개 만든 후에 남은 간선들을 어떤식으로 켜든 가능하게 할 수 있음. 스패닝 트리가 있고 남은 간선들은 어떻게든 사이클을 만들기 때문에 위에서의 그 간선 형태를 유지한채로 그 간선을 켜게 되면 그 간선이 트리와 만드는 사이클 간선들을 전부 반대로 해주면 된다고 함. 사이클은 홀짝성에 영향을 전혀 주지 않기 때문인 듯. 그래서 nCk * 2^(M-N+1) 

그래서 모든 Connected Component에 대해서 이걸 해준다음에 DP형식으로 처리해주면 된다... 라는데

솔직히 떠올리기 너무 어려워보인다. 어디서부터 시작을 해야할지도 감이 잘 안잡히는데 생각의 순서를 제대로 정리하지 않으면 자칫 꼬이기도 쉬운 문제라고 생각. 

E도 문제가 간단해서 보긴 봤는데.. 풀이가 잘 이해가 가지 않는다. 카르테시안 트리? 가 나오는데 이것에 대한 정보가 찾기 좀 힘듬.. 배워야되는건가 싶기도 하고

아무튼.. 현타가 좀 온다 D, E를 풀 수 있을때까지 실력 올릴 수 있을까? 싶음