AtraFelis's Develop Diary

문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다.A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.입력첫째 줄에 A, B ($1 ≤ A 출력A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.풀이BFS를 이용하여 최소 연산 횟수를 찾는 문제이다. 주의할 것은 B의 최댓값이 $10^9$이므로, 오버플로우가 일어날 수 있다는 것이다.첫 번째 연산인 $num \times 2$일 때는 int의 최댓값인 $2^{31}-1$을 초과하지 않지만, 두 번째 연산에서는 오버플로우가 일어날 수 있으므로 64bit 자료형인 long을 사용하거나, unsigned int를 사용해야 한다. 하지만..

SILVER II문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.풀이난이도 보고 쉽게 풀 수 있겠거니 했다가, 통수에 통수를 맞은 문제였다.일단 문제의 풀이 방향은 이렇다.주어지는 입력값을 그래프로 만든다.1번 노드부터(1번은 무조건 root이므로) 차례대로 그래프를 탐색한다. BFS든 DFS든 상관없으나 나는 BFS를 사용하였다.1번 노드와 연결된 노드는 무조건 1번 노드를 부모로 갖는다.이미 부모..

SILVER I 문제 여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가? MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과) MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다. 외향(E) / 내향(I) 감각(S) / 직관(N) 사고(T) / 감정(F) 판단(J) / 인식(P) 각 척도마다 두 가지 분류가 존재하므로, MBTI는 총 $2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자..

백준 5525 - IOIOI문제N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.P1 IOIP2 IOIOIP3 IOIOIOIPN IOIOI...OI (O가 N개)I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.출력S에 $P_N$이 몇 군데 포함되어 있는지 출력한다.제한$1 ≤ N ≤ 1,000,000$$2N+1 ≤ M ≤ 1,000,000$S는 I와 O로만 이루어져 있다.서브태스크번호배점제한150N ≤ 100, M ≤ 10 000.250추가적인 제약 조건이 없다.  풀이 시도 1모든 문자..