[백준 9440] 숫자 더하기
백준 9440번 : 숫자 더하기 www.acmicpc.net/problem/9440 9440번: 숫자 더하기 강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이는 이 문제의 답이 2 www.acmicpc.net /* 문제 설명 */ N(2 ≤ N ≤ 14)개의 0~9 사이의 숫자가 주어질 때, 숫자들을 조합하여 우선 두 개의 숫자를 만든다. 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수를 구하시오. /* 해결 방안 */ 두 숫자를 더했을 때, 최소가 되려면 어떻게 해야할까? 숫자의 앞에서 부터 뒤를 봤을 때, 큰 숫자를 어디로 배치해야할지 떠올려보자. 큰 숫자..
[백준 14939] 불 끄기
백준 14939번 : 불 끄기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net /* 문제 설명 */ 전구 켜져 있다 == 1, 꺼져 있다 == 0 10×10 배열이 있을 때, 한 칸을 누르면 그 위치에서 위, 아래, 왼쪽, 오른쪽에 있는 배열의 상태가 바뀌게 된다. 모든 배열을 0으로 만들기 위해서는 최소 몇 번 눌러야 하는가? /* 해결 방안 */ 가로가 10칸이고, 세로가 10칸 이므로, 총 100칸에 대해서 클릭할지 말지를 ..
[백준 2170] 선 긋기
백준 2170번 : 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net /* 문제 설명 */ 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없을 때, 그려진 선들의 총 길이를 구하시오. (선이 여러 번 그려진 곳은 한 번씩만 계산한다.) /* 해결 방안 */ 겹쳐진 선분들끼리 한 구간으로 합쳐나가다가, 마지막에 구간들의 길이만 세서 더해주자! → Sweeping /* 구현 과정 */ 1. 왼쪽 좌표를 기준으로 선을 ..