0과 1의 쉼터

문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.풀이T번 동안 1, 2, 3으로 정수 n을 만들기 위한 모든 경우의 수를 구하는 문제다.dp[i] : i를 만들 수 있는 경우의 수n을 구성하기 위해 문제에서 주어진 연산은 1, 2, 3을 합해서 만..

문제 https://www.acmicpc.net/problem/1463풀이N을 1로 만들기 위한 연산을 최소화하는 문제다.dp[i] : i를 만들기 위한 최소 연산 횟수기본적으로 dp[i]는 dp[i - 1]에 1을 더해 만들 수 있다, dp[i] = dp[i - 1] + 1i가 만약 2 또는 3의 배수라면, 1, 2번 연산에 의해 곱셈으로 계산하는게 이득이다.단, 2보다는 3으로 곱셈하는 것이 연산 횟수가 더 최소화되므로 dp 갱신 순서에 유의하자.소스코드보기

풀이루트가 1번인 트리에서 하나의 말을 "두 사람이 최적으로" 번갈아가며 점수를 얻고 말을 이동하는 문제다.문제에서 주어진 두 사람이 최적으로 라는 지문의 의미는 결국 시작 정점을 기준으로 자신의 점수를 가장 높이는 방향으로 게임을 끝내는 것을 의미한다. 우선 간선을 입력받아 양방향 그래프를 생성하자.이제 dfs로 리프노드까지 탐색하며 역순으로 부모노드에 대한 점수를 계산하고자 한다.양방향 그래프이므로 자식 노드로만 탐색을 해주자.리프노드 까지 탐색을 완료했다면 가장 적은 점수차를 dp에 갱신해주자.만약 자식이 없다면(리프노드) 자신의 번호가 자신의 점수가 되므로 diff를 0으로 계산해주자. 예선 3일차에서도 유명한 문제임에 비해 예외가 적용되지 않는 오류가 있었고, 제공되는 자료와 맞지않는 문제가 주..