맛있는감귤

문제 : https://www.acmicpc.net/problem/11657최단거리를 찾는 문제같은데 타임머신이 있거나 시간을 역행하는 문제, 음수 가중치가 존재하는 대다수의 문제는 벨만-포드 알고리즘으로 해결가능합니다.다익스트라 알고리즘 같은 경우 해당 노드에 존재하는 간선을 보고 가중치가 가장 작은 값을 선택하게 됩니다.그렇기 때문에A -> B -> C / A -> C 의 루트에서1 5 -4 1 3의 값을 가질 때 노드 A의 간선의 가중치 5와 3만을 비교하기 때문에 원하는 답을 도출할 수 없습니다.왜냐하면 1 -> 5 -> -4이 더 최단 거리가 되기 때문이죠.그렇기 때문에 간선을 비교하고 또 노드의 개수-1만큼 또 비교를 해주면 됩니다. (도착지 노드까지 가는 간선은 전체 노드개수를 넘지 않기 때..

문제 : https://www.acmicpc.net/problem/9517출처Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #2 1번 원형 식탁에서 210초를 넘겼을 때 폭탄을 가지고 있는 사람을 출력하면 됩니다.이렇게 원형인 구조가 있을 때는 %로 관리해주면 편하게 할 수 있습니다.저는 시작이 0이 아닌 1부터 시작이기 때문에 헷갈려서 처음 입력받을 때 -1 해주고 출력할 때 다시 +1 해주었습니다. #include int main(){ int pos, N, total_time = 210; scanf("%d %d",&pos, &N); --pos; for(int i=0;i

문제 : https://www.acmicpc.net/problem/1726출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 고등부 3번 명령어 go K의 의미를 잘못 해석해서 해맸었는데 결론은 총 다섯 가지 방법을 탐색하면 됩니다go 1, go 2, go 3, 90도 회전 -90도 회전.가장 중요한 것은 visited배열의 활용, 예외사항 판별, 실행 가능한 명령어 구분입니다.1. 방향 구분없이 이동만 한다면 좌표에 해당되는 2차원 visited배열을 만들었겠지만 방향이 존재하기 때문에 방향에 따른 visited배열을 추가하여 3차원 배열 생성2. 맵 이탈, 재방문, 궤도가 아닌 곳을 예외처리3. go 1,2,3 / 90도, -90도 회전먼저, 좌표와 방향, 그리고 명령어 횟..

문제 : 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])가 나옵니다. 이 중..