본문 바로가기

문제 해결/BOJ117

[백준] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 두 정점 사이의 경로가 가장 긴 값(트리의 지름)을 구하는 것이 이번 문제의 목표입니다. 트리의 특성상 부모 노드를 하나만 가질 수 있기 때문에 하나의 부모노드에서부터 자식 노드를 연결하여 만들 수 있는 최대 경로의 길이를 정할 수 있습니다. dfs로 탐색해주면서 현재 노드에서 도달할 수 있는 최대 길이를 리턴해주고 현재 노드에서 만날 수 있는 상위 2개의 최대 길이를 더해주면 트.. 2023. 2. 4.
[백준] 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 삼성 기출 문제의 경우 설계를 잘해야하는데 심신미약 상태에서 푸느라 설계부터 꼬여서 고생을 많이한 문제입니다. 포인트가 되는 부분은 상어의 다음 위치를 가져오는 next_pos 함수입니다. 핵심 포인트는 행이 1, R, 열이 1, C를 벗어나게 됐을 때 얼마나 벗어났는지 계산하여 반영해주어야하는게 포인트입니다. 왼쪽으로 향하다가 벗어나서 오른쪽으로 방향 전환하여 진행해도 격자를.. 2023. 2. 3.
[백준] 물대기 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제의 특징을 생각해봤을 때 논에 물을 끌어오려면 연결 그래프여야하고 각각의 연결 비용을 합쳤을 때 최소비용이 되어야하므로 자연스럽게 최소 신장 트리로 풀어야한다고 생각했습니다. 문제는 직접 논에 우물을 파는 것을 처리해야하는데 이 부분은 별도의 노드(코드에서는 other_node)를 만들어서 우물을 팔 때 발생하는 비용으로 각 노드와 연결시켰습니다. 이렇게 구축한 .. 2023. 2. 3.
[BOJ] 일요일 아침의 데이트 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제의 지문을 잘 읽어야하는 국어문제입니다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다. 라는 지문의 내용이 있는데 이 부분을 처리하지 않으면 잘못된 답이 나오게 됩니다. S, F인 경우에는 쓰레기에 인접해있지 않는 칸으로 처리하여 해결하면 됩니다. 큐에서 빠져나오는 우선순위를 정해주기 위해 우.. 2023. 2. 2.
[백준] 10986번 나머지 합 - python 문제 링크: https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 먼저 누적합을 구해줘야합니다. 그 다음 M으로 나누어 떨어지는 구간을 찾아야하는데 이 부분을 찾기 위해서 매번 구간을 정해서 구하게 되면 N = 10^6인 상태에서 O(N^2)이 되므로 시간 초과가 나게 됩니다. 그래서 다음과 같은 특성을 이용해야합니다. i ~ j 구간의 합을 구하게 되면 nums[i] - nums[j]가 되게 되는데 .. 2022. 9. 29.
[BOJ] 3980번 선발 명단 문제 출처: https://www.acmicpc.net/problem/3980 3980번: 선발 명단 문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다. 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100가지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다. 이때, 모든 선수의 포지션을 정하는 www.acmicpc.net 11명의 선수들이 각 포지션별로 능력치가 매겨져 있습니다. 11명의 선수들을 포지션을 잘 정해줘서 능력치의 합이 최대가 되.. 2019. 8. 20.
[BOJ] 1436번 영화감독 숌 문제 출처: https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조 www.acmicpc.net 간단하게 6이 연속으로 3번이상 나오는 수들을 작은 값부터 큰 값까지 순서를 매겨서 입력으로 주어진 순서의 수를 출력하면.. 2019. 8. 18.
[BOJ] 15683 감시 문제 출처: https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 이번에도 구현이 난해해 보여서 건너 뛰었던 부루트 포스 감시 문제를 풀어보았습니다. 종만북을 본 이후로 자신감이 붙은 것 같아.. 2019. 8. 17.
[BOJ] 14500 테트르미노 문제 출처: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 1X1 정사각형 네개를 이어 붙혀서 만들 수 있는 모양으로 칸을 덮었을 때 덮혀진 칸들의 값의 총합이 가장 클 때를 구.. 2019. 8. 17.

티스토리툴바