본문 바로가기
728x90

문제풀이/백준33

BOJ1931 회의실 배정 사용언어 C++ 문제 입력 출력 예제 입력 1 예제 출력 1 문제 풀이 이 문제는 그리디를 이용해 풀었습니다. 그리디는 현재의 값만을 통해 선택을 하는 방식입니다. 편하지만 그렇기 때문에 그 값이 최적의 값인지 항상 증명을 해주어야합니다. 다음과 같은 생각을 할 수 있을 겁니다. 1. 빨리 시작하는 걸 기준으로 선택하자? 조금만 생각해봐도 안되는 걸 알 수 있습니다. 2. 빨리 끝나는 걸 기준으로 선택하자? 이런식으로 빨리 끝나는 걸 선택해주면 조각조각이 나있는 회의들을 선택할 수 있습니다. 그리고 다음 회의의 시작시간이 현재 진행중인 회의의 끝나는 시간보다 빠른지를 체크해주면 문제를 풀 수 있습니다. 코드를 다음과 같습니다. 알고리즘 분류 그리디알고리즘 출처 : https://www.acmicpc.ne.. 2020. 8. 6.
BOJ1018 체스판 다시 칠하기 C++ 사용언어 C++ 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각.. 2020. 6. 21.
BOJ11650 좌표정렬2 C++ 사용언어 c++ 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 5 0 4 1 2 1 -1 2 2 3 3 예제 출력 1 1 -1 1 2 2 2 3 3 0 4 문제 풀이 되게 간단한 문제다 싶어서 금방 풀 줄 알았는데 계속 런타임 에러가 나더라구요. 심지어 c++ algori.. 2020. 6. 20.
BOJ2231 분해합 사용언어 c++ 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력 1 216 예제 출력 1 198 문제 풀이 알고리즘 분류 브루트 .. 2020. 6. 18.
728x90