[BOJ] 백준 17266. 어두운 굴다리

2024. 5. 31. 21:24· Java/BOJ

문제

https://www.acmicpc.net/problem/17266


풀이

세 가지 구역을 체크했습니다. 길 시작점부터 첫 가로등까지의 구역, 가로등과 가로등 사이의 구역, 그리고 마지막 가로등과 도착점의 구역입니다.

 

 세 가지 구역의 특징은 가로등과 가로등 사이면, 사이의 구간을 두 개의 가로등이 절반씩 나눠서 커버할 수 있다는 것이고 시작 구역과 도착 구역은 가로등 하나가 온전히 구간을 커버해야합니다. 

 

 그래서 아래처럼 세 구간으로 나누어 커버 범위의 최대 값을 구해주었습니다. 주의해야할 것은 만약 가로등과 가로등 사이 구간의 길이가 홀수라면, 사이의 길이/2 +1을 해주어야 한다는 것입니다. 홀수를 2로 나누기만 하면 중간을 커버하지 못하게 됩니다. (3이면 3/2 -> 1, 그러나 3을 1 두개로 커버하지 못함.)

 

 아래는 소스 코드입니다.


소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int firstDiff = sc.nextInt();
        int lastDiff = N;

        int maxDiff = 0;
        int tmp = firstDiff;
        for(int i = 1;i<M;i++){
            int x = sc.nextInt();
            maxDiff = Math.max(maxDiff,x-tmp);
            tmp = x;
            lastDiff = N-x;
        }
        int diff = 0;
        if(maxDiff%2==1) diff = maxDiff/2+1;
        else diff = maxDiff/2;
        
        int ans = Math.max(firstDiff,Math.max(lastDiff,diff));
        System.out.println(ans);
    }
}

'Java > BOJ' 카테고리의 다른 글

[BOJ] 백준 20310. 타노스  (0) 2024.06.21
[BOJ] 백준 1138. 한 줄로 서기  (0) 2024.06.10
[BOJ] 백준 17135. 캐슬 디펜스  (0) 2024.05.29
[BOJ] 백준 10164. 격자상의 경로  (0) 2024.05.28
[BOJ] 백준 14890. 경사로  (0) 2024.05.27
'Java/BOJ' 카테고리의 다른 글
  • [BOJ] 백준 20310. 타노스
  • [BOJ] 백준 1138. 한 줄로 서기
  • [BOJ] 백준 17135. 캐슬 디펜스
  • [BOJ] 백준 10164. 격자상의 경로
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 이석복
  • 자바
  • 스택
  • OS
  • 한양대
  • 백준
  • Java
  • 네트워크
  • 인프런
  • 구현
  • 자바스크립트
  • 운영체제
  • 프로그래머스
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 큐
  • JCF
  • BOJ
  • 반효경
  • 레디스
  • 김영한

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 17266. 어두운 굴다리
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.