맛있는감귤

문제 : https://www.acmicpc.net/problem/1991트리 순회 문제입니다.각 순회에 대한 정의는 위키피디아를 참조했습니다.https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C전위 순회전위 순회(preorder)는 다음과 같은 방법으로 진행한다. 루트 노드에서 시작해서,노드를 방문한다.왼쪽 서브 트리를 전위 순회한다.오른쪽 서브 트리를 전위 순회한다.전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.중위 순회중위 순회(Inorder Traversal)은 다음의 순서로 진행된다.왼쪽 서브 트리를 중위 순회한다.노드를 방문한다.오른쪽 서브 트리를 중위 순회한다.중위 순회는 대칭 순회(symm..

문제 : https://www.acmicpc.net/problem/2579첫 번째 계단부터 최대점수를 구하고... 두 번째 계단의 최대점수 구하고.......마지막 계단의 최대 점수를 구하는 DP문제입니다.첫번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟았을 때 받게 되는 점수가 됩니다. sum[1] = step[1]두번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟고 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟지않고 2단 점프를 했을 때가 됩니다.세번째 계단 또한 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟고 세번째계단으로 2단점프를 했을 때가 됩니다.N번째 계단은 N-3번째 계단에서 N-1번째 계단까지 2단점프를 한 후, N번째 계단으로 점프를 했을 때 혹은 N-2번째 계단에서 2단점프를 했..

문제 : https://www.acmicpc.net/problem/10651의 자리수가 한수에 해당되는지 헷갈렸는데 테스트 인풋을 보니 1의 자리수도 한수에 해당되는 것을 알 수 있습니다.그렇게 되면 100이하의 수는 무조건 한수이기 때문에 N 100 일 때는 백의자리수-십의자리수와 십의자리수-일의자리수가 항상 같은 값을 가질 때만 카운팅해주면 쉽게 답을 도출해낼 수 있습니다. #include int main(){ int N, cnt=99; scanf("%d",&N); if(N < 100) { printf("%d\n",N); return 0; } for(int i=100;i

문제 : https://www.acmicpc.net/problem/1015입력으로 주어진 배열 A의 index가 수열 P에 해당됩니다.그렇기 때문에 pair로 묶어 정렬했을 때 i값이 배열 B에 해당하는 수열 P가 됩니다. #include #include #include using namespace std; int N, B[51]; vector v; int main(){ scanf("%d",&N); for(int i=0;i

문제 : https://www.acmicpc.net/problem/1551수열 Ai 가 주어졌을 때 계차수열 Bi를 구하는 과정을 N번 반복하는 문제입니다. #include int main(){ int N,K,A[21]; scanf("%d%d",&N,&K); getchar(); for(int i=0;i

문제 : https://www.acmicpc.net/problem/11052 기초 DP문제입니다. 여느 DP 문제가 그렇듯이 가장 작은 수부터 고려해 점차 큰 수일 때 경우를 고려하는 Bottom-Up 방식으로 풀면됩니다. DP에서 가장 중요한 것은 메모이제이션 그리고 점화식이죠. 예를 들어, 첫 번째 테스트 입력을 보겠습니다.4 1 5 6 7먼저 붕어빵 개수 당 가격을 담고 있는 fish[4] 배열과 각 수의 팔았을 때 가장 큰 값을 가진 배열 sum[4]가 있다고 봅시다. 먼저 붕어빵 한개를 팔때 가장 비싸게 파는 sum[1] = fish[1]가 되겠죠. 그 다음 붕어빵 두개를 팔 때는 두개에 파는 가격 fish[2]와 한 개 값으로 두 개를 파는 경우(sum[1]+fish[1])가 나옵니다. 이 중..

문제 : https://www.acmicpc.net/problem/1759조건을 만족하는 부분집합을 출력하는 문제입니다. 일반적으로 dfs로 많이 풀긴하는데 저는 비트마스크로 해결했습니다.최소 모음 1개, 자음 2개 이상을 포함한 구문만 출력해야된다는 것만 명심하시면 될 것 같습니다.비슷한 문제로 로또 문제가 있습니다.https://www.acmicpc.net/problem/6603 #include #include #include using namespace std; int L,C; char c[16]; void code(int n){ int place[16], consonants = 0, vowels = 0; int a = n, cnt = 0; for(int i=C-1;i>=0;i--){ place[i..

문제 : https://www.acmicpc.net/problem/2583출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번 저는 맵을 만든 후 사각형 부분은 전부 1로 하고 나머지 0이 되는 부분만 DFS를 이용하여 넓이를 구한 후 벡터에 넣어주고 사이즈( 사각형의 개수)를 출력 한 뒤 정렬하여 넓이를 출력했지만 우선순위 큐에 넣으면 간단하게 해결됩니다. #include &ltiostream&gt #include &ltalgorithm&gt #include &ltvector&gt using namespace std; int M,N,K; bool map[102][102]; bool isVisited[102][102]; vector&ltint&gt v; int px[..

문제 : https://www.acmicpc.net/problem/1967한 노드를 기준으로 가지고 있는 말단 노드를 쫙 땡겼을 때 가장 긴 녀석의 지름을 구하는 문제입니다.자식 노드가 3개 이상일 수 있다는 것만 조심하시면 DFS로 간단하게 해결 가능합니다.자식 노드의 가중치의 합을 return 하여 기준 노드에서 가장 긴노드, 두 번째 노드를 구해서 더한 값이 지름이 됩니다. #include #include using namespace std; int N, ans=0; vector v[10001]; int dfs(int start){ int fst=0, snd=0, sum; for (auto n : v[start]){ //printf("%d %d\n",start,n.second+len); sum = ..

문제 : https://www.acmicpc.net/problem/1193간단한 문제라고 생각했는데 생각보다 애먹은 문제였습니다.수학적 공식이 있지 않을까 찾다가 포기하고 좀 무식하게 직관적으로 해결했습니다.대각선을 하나의 군으로 봤을 때, 군의 갯수는 n의 개수만큼 있습니다. 게다가 홀수와 짝수에 따라 방향이 달라지는 것도 포인트입니다.그렇기 때문에 홀수일 경우 N/1로 시작해 분자A를 -- 분모B를 ++해주면 되고 짝수일 경우엔 반대로 해주면 됩니다. #include int main(){ int X,n=1,cnt=0,A=1,B=1; scanf("%d",&X); while(1){ if(n%2==0) A=1, B=n; else A=n, B=1; for(int i=0;i