알고리즘 부수기

문제링크 : https://codeforces.com/contest/1099/problem/D 결론부터 말하자면 틀린 문제이다. 당연하다고 생각하고 여러 가지를 다시 생각해보지 않았기 때문에 제대로 풀지 못했다. - 노드의 개수 (n) - 2번부터 노드의 parent 노드 번호 - 1번부터 노드의 S_v (해당 노드부터 루트까지 경로상에 있는 모든 노드의 value 합) [ 단, 루트의 height을 1이라고 할 때 height이 짝수인 칸은 -1로 주어짐 ] - 해당 트리에서 모든 노드의 value들의 합 중 최소값 (조건에 맞는 트리가 될 수 없을 경우 -1) 문제의 상황은 height이 짝수인 노드들의 루트까지의 sum을 -1로 바꿔버린 상황이다. 즉, height이 홀수인 칸은 맞는 sum들이 들..

문제링크 : https://codeforces.com/contest/1099/problem/C - '?'와 '*'이 포함된 문자열 - 만들고 싶은 문자열 길이 - ?와 *의 기능을 이용해서 원하는 길이로 만들어진 문자열 - 불가능할 경우 Impossible 내가 알고리즘 문제를 풀 때 가장 어려워하는 문자열 가지고 놀기 문제이다. 먼저, '?'와 '*'의 기능을 살펴보자. '?'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있다. '*'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있고 추가로 원하는 개수만큼 복사할 수 있다. 주어진 문자열에서 기호의 기능을 사용해 만들 수 있는 많은 문자열 중 아무거나 하나만 출력해도 된다. 이 조건이 문제를 굉장히 쉬워지게 만들었다. 3가지 경우로 나눠서 ..

문제링크 : https://codeforces.com/contest/1099/problem/B 원하는 개수의 사각형을 만들기 위해 자를 재고 그려야하는 선의 개수의 최소값을 찾는 문제이다. 우선 이해하기 쉽게 문제를 설명해보면, 위 그림에서 빨강색 선은 자를 이용해서 그려야 하는 부분, 검정색은 자 없이도 그릴 수 있는 부분이다. 왜 검정색은 자 없이 그릴 수 있는 부분인가? 이미 같은 x 와 (x+1) 혹은 같은 y와 (y+1)을 이은 선이 존재하기 때문이다. 즉, a'은 a로 인해 자 없이 그릴 수 있고, b'은 b로 인해 자 없이 그릴 수 있게 된다. 마찬가지로 사각형 2개를 만들기 위해서는 아래 그림과 같이 구성되어야 한다. 사각형 2개를 만들기 위해서는 3개의 빨강 선이 필요하게 된다. 이제, ..

2018년 마지막 코포(Good Bye 2018)를 끝냈습니다. 그린으로 떨어져서 마지막 코포에서 민트 만들고 끝내고 싶었는데.. 같은 문제에서 1시간 10분동안 10번 제출해도 같은 곳에서 계속 틀렸습니다. 결국 맞은 다음에 알고 보니 long long으로 선언해놓고 %d로 계속 출력.. 이런 실수도 못 찾아내는거 보면 아직 멀었네요T^T 너무나 멘붕이 와서 이번에 푼 문제는 올리지 않는걸로.. 흑 (이렇게 점수 깎여놓고 Rating 2점 내려가는거 보니 너무 아쉽.. 만약이란 없지만 맞췄으면 떡상..) 2019년에는 반드시 블루로 올라가겠습니다 !!!

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/C 입력으로 특정 각도가 주어진다. 이 때, 정다각형 내부에서 위와 같이 3개의 점을 연결해서 주어진 각도를 만들 수 있는 정n각형들 중 최소인 n을 찾는 문제이다. 우선, 수학적으로 알아야할 개념이 있다. 정n각형의 내각의 총 합 : 180 * (n-2) 위의 공식을 따라 (180 * (n-2)) / n 을 통해 정n각형의 한 각의 크기를 알 수 있다. 다음으로 알아야할 내용은 정n각형의 특징이다. 정사각형을 생각해보자. 정사각형에서 한 점에 대해 위 그림과 같이 추가적으로 이어줄 수 있는 점은 양 옆을 제외한 나머지 1개의 점( n-2 )이다. 이어줄 경우 정사각형의 한 각의 크기인 90도를 정확히 1..

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/B 이번 코포는 자료형과 관련된 것들을 제대로 다룰줄 모르면 헤맬 수 밖에 없었다. 이 문제에 대한 설명부터 하자면 최소 2개 이상의 문자로 구성된 string이 왔을 때, substring을 빼서 한 글자만 남아있거나 아무 것도 없게 만드는 경우의 수를 구하는 것이다. 얼핏 보면 "전체 다 따져야하나?"라는 생각이 들지만 substring이라는 것을 기억해야 한다. substring은 부분 문자열이다. 즉, 연결되어 있는 문자열 1개를 제거한다는 뜻이다. 그럼 이제 문제를 다시 보자. 우리는 특정 1종류의 문자만 남도록 혹은 하나도 남지 않도록 만들어야 한다. 크게 3가지 경우로 나눌 수 있다. i) 앞..

D번) 문제 링크 : http://codeforces.com/contest/1095/problem/D n개의 노드가 존재한다. 이 때, 순서에 상관없이 각 노드마다 자기 다음에 있는 노드 2개를 알려준다. ex) 입력을 해석해보면1번 노드의 뒤에는 3과 5가 오고2번 노드의 뒤에는 1과 43번 노드의 뒤에는 2와 44번 노드의 뒤에는 1과 55번 노드의 뒤에는 2와 3이 온다. 이 때, 이 정보를 바탕으로 올바른 순서를 찾으면 되는 문제이다. 접근 방법은 단순하다. node라는 구조체를 만들어서 다음 값 2개를 저장한다.그리고 set함수와 값을 하나 줬을 때 다음 값 2개 중 해당 값이 있는지를 확인하는 함수를 만든다. 다음으로 출력하는 순서는 상관없다고 했으므로 1번 노드부터 시작해서 다음 1번노드가 ..

C번) 문제 링크 : http://codeforces.com/contest/1095/problem/C 문제의 입력으로는 n과 k가 주어진다. 쉽게 설명해서 주어진 숫자 n을 k개의 2의 거듭제곱의 합으로 나누는 것이다. 사용한 방법은 우선 k와 상관없이 필요한 최소한의 개수를 구하는 것이다. ex) n=9, k=4라고 하자. 이 때, 필요한 최소한의 개수는 1과 8 즉, 2개이다. 최소한의 개수가 구해졌다는 것은 2의 거듭제곱 형태로 나타낼 수 있다는 것이다. 이 형태는 2진수의 형태에서 1인 값들과 동일하다. 여기까지만 생각하고 바로 YES를 출력해서는 안된다. 문제에서 요구하는 YES/NO의 조건은 2의 거듭제곱의 합 형태로 나타낼 수 있느냐가 아닌 k개의 2의 거듭제곱의 합으로 나타낼 수 있느냐이다..