본문 바로가기
반응형

acmicpc43

백준 #1103 게임 숫자가 써져있는 보드의 맨 왼쪽 위에 돌이 있고, 그 칸에 써져있는 숫자만큼 돌을 상하좌우로 옮길 수 있습니다. 이 게임은 돌이 보드 중간에 있는 구멍 또는 밖으로 나가게 되면 끝나게 됩니다. 돌의 위치에서 판단할 때, 가장 오랫동안 돌을 움직이기 위해서는 모든 경우를 생각해야 합니다. 또는 돌이 지나왔던 칸으로 다시 돌아온다면, 그 게임을 무한하게 즐길 수도 있습니다. 난이도는 Gold I입니다. 사실 생각보다 난이도가 높습니다. 맞은 사람 548명, 정답비율 17.6%. 이 문제는 모든 경우를 찾으면 반드시 시간초과로 실패하게 됩니다. 그렇다고 모든 경우를 찾지 않으면 안 됩니다. 모순이죠? 다행히 자신이 왔던 자리로 돌아오면, 사이클을 이루기 때문에 그 상태에서는 더 조사할 필요가 없습니다. 또한 .. 2020. 1. 2.
백준 #1083 소트(정렬) 이번 문제는 버블 정렬을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제입니다. 난이도가 Gold IV이긴 하지만 더 낮아져도 상관 없을 문제라고 봅니다. 정답비율은 30.5% 정도로 높지가 않습니다. 정답자 184명. https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다. www.acmicpc.net 버블 정렬은 이해하기 아주 쉬운 정렬이고, 구현도 쉽게 할 수 있죠. 버블정렬은 이웃한 것끼리 위치를 바꾼다는 개념입니다. 키 순으로 줄을 설 때.. 2019. 12. 31.
백준 #1081 합 숫자가 주어지면, 숫자에 있는 모든 자릿수의 합을 구할 수 있습니다. 예를 들어서 \(47 \to 4+7=11\)이 됩니다. 이 문제는 주어진 숫자 범위에 있는 모든 수에 대한 자릿수의 합을 구하는 것입니다. 이미 이 문제는 #1019에서 다루었던 것입니다. 단지 다른 것은 #1019 문제는 1부터 주어진 숫자까지의 자릿수 합이지만, 여기서는 시작하는 숫자가 주어진다는 것뿐입니다. #1019는 모든 자릿수들의 빈도를 출력하는 것이지만, 이 문제는 합을 표현하는 것입니다. 아이러니하게 #1019는 난이도가 Gold I 이지만, 이문제는 두단계 낮은 Gold III입니다. https://www.acmicpc.net/problem/1081 1081번: 합 첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같.. 2019. 12. 31.
백준 #1074 Z 이번 문제는 자기 복제 개념이 들어가 있는 문제입니다. 큰 모양에서도 Z를 이루고, 작은 모양에서도 Z를 이루는 형태로 배열을 채울 때, 주어진 행과 열에 어떤 숫자가 있는지 알아내는 문제입니다. 난이도는 Silver I입니다. 위의 그림과 같이 2x2라면 Z 모양대로 숫자를 배치합니다. 그런데 배열 갯수가 늘어나면, 과 같이 복잡한 형태가 됩니다. 여기서 주어진 칸의 숫자를 알아내면 됩니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N .. 2019. 12. 30.
백준 #1068 트리 이번 문제는 트리에서 어떤 노드를 삭제하고 나서의 말단 노드(leaf node)의 갯수를 구하는 것입니다. 위의 그림에서처럼 트리가 있는데, 1번 노드를 삭제하면, 3번 노드와 4번 노드도 같이 삭제되어서 2번 노드 하나만 말단 노드가 됩니다. 그 갯수를 구하면 됩니다. 난이도는 Silver I으로 되어 있지만, 구현은 어렵지는 않습니다. 문제의 원 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acm.. 2019. 12. 30.
백준 #1057 토너먼트 토너먼트 경기는 두개의 팀 또는 선수가 싸워서 이기면 한단계씩 올라가는 경기입니다. 기본적으로 이진트리 형태를 가지고 있습니다. 문제의 내용은, 1부터 N까지 선수들을 일렬로 세웠을 때, A번 선수와 B번 선수가 언제 경기를 하게 될 수 있는지를 찾는 것입니다. 이게 이진 트리라는 성격을 알면 의외로 쉽게 풀 수 있습니다. Silver II 문제로 되어 있지만 그보다는 난이도는 너 낮다고 보입니다. 그림과 같은 토너먼트 표가 있다고 하고, 왼쪽부터 1, 2, 3, 4, 5, 6, 7, 8 이라고 숫자가 매겨졌다고 해보죠. 대한민국은 5번이 됩니다. 그런데 캐나다와는 언제 붙을 가능성이 있는지 알아보자고 한다면, 캐나다는 2번에 있습니다. 그러면 결승에 가서야 캐나다와 경기할 가능성이 있습니다. 대한민국과.. 2019. 12. 29.
728x90

티스토리툴바