문제 노트/정올 (47) 썸네일형 리스트형 화살표 그리기( 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개가 필요하다는 걸 알 수 있습니다. 하지만 우리가 설계한 .. 딱지놀이( BOJ 14696 ) 문제 : https://www.acmicpc.net/problem/14696 14696번: 딱지놀이 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 딱지놀이의 총 라운드 수를 나타내는 자연수 N이 주어진다. N 은 1 이상 1,000 이하이다. 다음 줄에는 라운드 1에서 어린이 A가 내는 딱지에 나 www.acmicpc.net 문제 파악하기 A와 B의 딱지놀이 결과를 출력하는 문제입니다. 딱지에는 별(★), 동그라미(●), 네모(■), 세모(▲) 중 하나의 그림이 그려져있으며 우리는 A와 B가 가지고 있는 모든 딱지의 개수를 파악하여 승패를 알아내야 합니다. 승패를 가르는 중요한 요소는 바로 그림의 가중치라고 할 수 있습니다. 모든 그림에는 각기 다른 가중치가 부여되어 있으며, 그림 사이의 대소관계.. 369 게임( BOJ 10802 ) 문제 : https://www.acmicpc.net/problem/10802 10802번: 369 게임 여러 사람이 둘러 앉아 즐기는 369 게임은 다음과 같은 규칙을 가지고 있다. 규칙: 양의 정수 A에서 시작하여 차례로 사람들 이 돌아가면서 숫자를 하나씩 증가하면서 불러 나간다. 단, 부르는 숫 www.acmicpc.net 문제 파악하기 369게임을 진행 하면서 특정 구간동안 몇 번의 박수를 치는지 구하는 문제입니다. 기존에는 숫자에 3, 6, 9 중 하나라도 포함된다면 박수치는 규칙에서 3의 배수이면 박수를 친다는 새로운 규칙이 추가되었습니다. 물론 반복문을 사용하면 손쉽게 구할 수 있지만 입력되는 숫자의 범위가 너무도 크기 때문에 새로운 알고리즘이 필요합니다. 문제 해결하기 이 문제는 결국 A ~.. 막대기( BOJ 17608 ) 문제 : https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 파악하기 막대기를 일렬로 세운 후 오른쪽에서 바라보았을 때, 보이는 막대기의 개수를 출력하는 문제입니다. 오른쪽에서 보인다는 의미는 막대기의 높이가 오른쪽부터 순차적으로 증가해야 한다는 걸 말하며, 보이는 막대기의 총 개수를 구하기 위해서는 오른쪽부터 탐색을 시작하면 됩니다. 문제 해결하기 막대기가 보인다는 건 기존 가장 높았던 막대기보다 좀 더 크다는 의미입니다. 따라서, 지금까지 가장.. 369( BOJ 17614 ) 문제 : https://www.acmicpc.net/problem/17614 17614번: 369 민수는 같은 반 친구들과 369게임을 하고 있다. 369게임은 여러 명이 원형으로 둘러 앉아 시작 위치의 사람이 1을 외치며 시작된다. 이후 시계방향으로 돌아가며 2, 3, 4와 같이 1씩 증가된 수가 자 www.acmicpc.net 문제 파악하기 1부터 시작해서 N까지 369 게임이 진행되었을 때, 나오는 모든 박수의 수를 구하는 전형적인 문제입니다. N의 범위가 최대 106이기 때문에 단순히 반복문을 사용하면 문제를 해결할 수 있습니다. 문제 해결하기 369 게임은 숫자에 3, 6, 9가 포함된 개수만큼 박수를 쳐야 하는 게임입니다. 따라서, 1부터 N까지 숫자를 모두 확인하면서 범위 내 숫자 i에 3,.. 이전 1 2 3 4 5 6 다음