본문 바로가기

분류 전체보기

 (191)
양팔저울( BOJ 17610 ) 문제 : https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 문제 파악하기 양팔저울을 사용하여 측정할 수 없는 물의 무게가 몇 개인지 찾아내는 문제입니다. 양팔저울은 딱 1번 사용할 수 있으며, 물을 담을 수 있는 접시는 왼쪽 혹은 오른쪽 상관없이 올릴 수 있습니다. 우리는 추의 개수가 최대 13개라는 점에 주목하면 문제를 해결할 실마리를 찾을 수 있습니다. 문제 해결하기 추의 개수가 최대 13개라면 나올 수 있는 모든 경우의 수는 총 313 =..
Construct a Palindrome( Atcoder 196-F ) 문제 : https://atcoder.jp/contests/abc197/tasks/abc197_f F - Construct a Palindrome AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 1번 정점부터 시작해서 N번 정점까지 이동하면서 팰린드롬을 만들 수 있는지 없는지, 그리고 만약 만들 수 있다면 그 때의 최소 길이는 얼마인지 찾는 문제입니다. M개의 간선에는 각각 알파벳이 적혀있으며, 경로 상의 간선들에 적힌 알파벳을 나열하면 하나의 문자열이 나옵니다. 이 문자열이 팰린드롬인지, 그리고 만약 팰린..
Traveler( Atcoder 196-E ) 문제 : https://atcoder.jp/contests/abc197/tasks/abc197_e E - Traveler AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 수직선 위에 있는 공을 ID 순서대로 가져오는데 걸리는 최소 시간을 구하는 문제입니다. 출발은 0에서 시작하며 모든 공을 가진 다음에는 출발점인 0으로 돌아와야 합니다. 공은 한 곳에 여러 개 존재할 수 없지만 ID가 동일한 공은 여러 개 있을 수 있으며, ID가 작은 공부터 가져와야 합니다. 공의 개수가 최대 200,000개이기 때문에 완..
Opposite( Atcoder 196-D ) 문제 : https://atcoder.jp/contests/abc197/tasks/abc197_d D - Opposite AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 N개의 꼭지점으로 만들어진 정N각형 도형이 있다고 합니다. N개의 꼭지점 중 점 P0(x0, y0)과 PN/2(xN/2, yN/2)가 주어질 때, P1의 위치를 구하는 문제입니다. 문제에서 제공하는 건 2개의 점과 반시계방향으로 번호를 매긴다는 조건입니다. 우리는 이 조건을 이용해서 P0 바로 옆에 있는 P1의 좌표를 구해야 합니다. 이 때..
화살표 그리기( BOJ 15975 -고등 ) 문제 : https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net 문제 파악하기 두 개의 점을 같은 색이면서 가장 인접한 점과 연결하여 화살표를 만든 후, 만들어진 화살표 길이의 합을 구하는 문제입니다. 2018년 초등 문제인 화살표 그리기( https://www.acmicpc.net/problem/15970 )와 동일하지만 입력되는 점의 개수가 대폭 늘어난 문제입니다. 초등 문제는 단순히 완전 탐색을 통해 문제를 해결했습니다...
화살표 그리기( BOJ 15970 - 초등 ) 문제 : https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 문제 파악하기 N개의 점을 가장 인접한 같은 색깔 점과 연결하여 만든 화살표 길이의 합을 구하는 문제입니다. 점은 항상 같은 색깔인 점과 연결할 수 있으며, 가장 인접한 점을 찾아 그 사이의 길이를 구해야 합니다. 이 문제의 경우, N의 크기가 최대 5,000이하로 주어지기 때문에 가장 단순한 방법인 완전탐색을 통해 문제를 해결할 수 있습니다. 문제 해결하기 하나의 점 마다 좌표..
행복( BOJ 15969 ) 문제 : https://www.acmicpc.net/problem/15969 15969번: 행복 모든 서브태스크에서 2 ≤ N ≤ 1,000이고 입력되는 학생들의 점수는 0 이상 1,000 이하의 정수이다. www.acmicpc.net 문제 파악하기 N개의 학생들의 점수 중 최댓값과 최솟값을 찾아내는 문제입니다. 알고리즘을 공부하는 학생들이 가장 먼저 배우는 알고리즘이라고 할 수 있는 최댓값/최솟값 탐색 문제라고 할 수 있습니다. 문제 해결하기 최댓값과 최솟값을 찾는 방법에는 여러가지 있습니다. 다만, 이번 문제에서는 가장 기본적인 방법인 초깃값 설정 후 탐색을 통한 방법을 소개해드리겠습니다. N개의 숫자 중 최솟값과 최댓값을 찾기 위해서는 N개의 숫자를 살펴보면서 현재 숫자가 지금까지 확인한 숫자 중 ..
방 배정하기( BOJ 14697 ) 문제 : https://www.acmicpc.net/problem/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 문제 파악하기 3개의 방에 N명의 학생들을 빈침대 없이 딱 떨어지게 배치할 수 있는지 판단하는 문제입니다. 단순히 가장 큰 방부터 넣는걸 생각하면 틀리는 문제입니다. 예를 들어 3개의 방에 침대가 각각 { 10, 8, 3 }개 있으며, 학생이 총 12명 있다고 생각해봅시다. 그러면 우리는 12명이니 3개의 침대가 있는 방 4개가 필요하다는 걸 알 수 있습니다. 하지만 우리가 설계한 ..

티스토리툴바