[백준/파이썬(Python), 자바(JAVA)] 수리공 항승 1449(Silver 3)

💌문제 

---

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

1449번: 수리공 항승

 

💌풀이

---

물이 새는 곳을 편의상 창문이라고 칭하겠다.

창문이 있는 위치는 제각각으로 들어오기 때문에, 연산하기 쉽도록 처음에 정렬을 하고 시작한다.

물을 막을 때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 한다고 했기 때문에, x-0.5와 x+0.5까지를 고려하며 계산해야 한다.

만약 테이프의 길이가 최대 1이라면, (x+0.5)-(x-0.5)=1이기 때문에 테이프는 창문의 갯수만큼 필요하다. 그래서 바로 n을 출력하고 끝낸다.

그게 아니라면 계산이 필요한데,

first에 우선 가장 첫 번째 원소-0.5 값을 넣는다. 그 후 루프를 돌면서 current에 항상 현재 원소+0.5 값을 넣는다.

만약 current-first 값이 테이프 길이와 같다면, 현재 원소 위치까지 테이프를 붙일 수 있다는 뜻이다. 그래서 answer에 1을 더해준다.

그리고 지금 인덱스가 마지막이라면 바로 answer를 출력하고 프로그램을 종료한다. 마지막이 아니고 더 봐야할 창문이 있다면 first에 다음 원소-0.5 값을 넣고 계속 연산을 수행해줘야 한다.

그리고 current-first 값이 테이프 길이보다 크다면, 현재 창문까지는 테이프를 다 붙일 수 없다는 것을 의미한다. 하지만 이전 창문까지는 테이프를 붙일 수 있기 때문에, answer에 1을 더해준다. 그리고 first에는 현재 원소-0.5 값을 저장해둔다. 그러면 다음 루프에서 현재 원소부터 다시 연산을 해줄 것이다.

최종적으로는 answer+1을 출력해준다. 왜냐면 마지막 인덱스에서 테이프 갯수를 추가시키고 끝나지 않았다면, 아직 테이프를 붙이기 전으로 루프가 끝났기 때문이다. 만약에 elif문에서 걸려서 테이프를 1 증가 시켰어도, 마지막 창문은 남아있기 때문에 하여간 마지막 창문을 더해줘야 한다. 그래서 1 더해서 출력한다.

 

💌파이썬 코드

---

n,l=map(int,input().split())
num=list(map(int,input().split()))

num.sort()
tape=1
answer=0
if l==1:
    print(n)
    exit()
current=num[0]-0.5 #신경 안 써도 됨 초기화하려고 넣은 것
first=num[0]-0.5

for i in range(n):
    current=num[i]+0.5
    if current-first==l:
        answer+=1
        if i!=n-1:
            first=num[i+1]-0.5
        else:
            print(answer)
            exit()
    elif current-first>l:
        answer+=1
        first=num[i]-0.5
print(answer+1)

 

💌자바 코드

---

package ch1;
import java.util.*;
import java.io.*;

class Main{
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int l=Integer.parseInt(st.nextToken());
		
		if(l==1) {
			System.out.println(n);
			return;
		}
		
		int ans=0;
		int[] num=new int[n];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<num.length;i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(num);
		int current=0;
		int first=(int)(num[0]-0.5);
		for(int i=0;i<num.length;i++) {
			current=(int)(num[i]+0.5);
			if (current-first==l) {
				ans++;
				if(i==num.length-1) {
					System.out.println(ans);
					return;
				}else {
					first=(int)(num[i+1]-0.5);
				}
			}else if (current-first>l) {
				ans++;
				first=(int)(num[i]-0.5);
			}
		}
		System.out.println(ans+1);
		
	}
}

💌다른 사람 코드

---

다른 사람들은 훨씬 간단하게 풀었다…

import sys

input = sys.stdin.readline

N , L = map(int, input().split())
arr = list(map(int, input().split(' ')))
arr.sort()

start = arr[0]-0.5
end = start + L
cnt = 1
for i in range(0, len(arr)): 
  if start< arr[i] < end:
    continue
  else:
    cnt+=1
    start = arr[i]-0.5
    end = start + L

print(cnt)

[백준 python] 1449번 수리공 항승 - 그리디

[백준 python] 1449번 수리공 항승 - 그리디