본문 바로가기

Algorithms/PS

 (29)
[PS] 백준 #14500. 테트로미노 문제 정보 난이도: 골드 V 문제 주소: https://www.acmicpc.net/problem/14500 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 ..
[PS] 백준 #19539. 사과나무 문제 정보 난이도: 실버 I 문제 주소: https://www.acmicpc.net/problem/19539 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 $1$번부터 $N$번까지 심었다. 이 나무들의 초기 높이는 모두 $0$이다. 사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 $2$개를 준비했다. 한 물뿌리개는 나무 하나를 $1$만큼 성장시키고, 다른 물뿌리개는 나무 하나를 $2$만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 $3$만큼 키울 수도 있다. 물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다..
[PS] 백준 #16937. 두 스티커 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/16937 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다. 오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다. 두 스티커가 붙여진 넓이의 최댓값을 구해보자. 나의 풀이 브루트포스로 모든 두 쌍의 스티커마다 붙일..
[PS] 백준 #20044. Project Teams 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/20044 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라. 문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면..
[PS] 백준 #1018. 체스판 다시 칠하기 문제 정보 난이도: 실버 V 문제 주소: https://www.acmicpc.net/problem/1018 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은..
[PS] 백준 #2798. 블랙잭 문제 정보 난이도: 브론즈 II 문제 주소: https://www.acmicpc.net/problem/2798 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라..
[PS] 백준 #14496. 그대, 그머가 되어 문제 정보 난이도: 실버 I 문제 주소: https://www.acmicpc.net/problem/14496 이 문제를 푼 이유: 그룹 연습 Div.2 문제 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다. 야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다. 예를 들어보자. (a, b), (a, c),..
[PS] 백준 #9417. 최대 GCD 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/9417 이 문제를 푼 이유: 그룹 연습 Div.2 문제 정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오. 나의 풀이 이 문제는 보자마자 브루트포스로 모든 쌍에 대해서 유클리드 호제법을 적용하여 최대 공약수를 구한 뒤 그 중 최대값을 구하면 되겠다고 생각했다. (최대 정수의 개수가 100이므로 4500쌍이 최대기 때문에 모든 경우의 수를 구해도 된다.) 하지만 이 문제에서 예상치 못하게 시간을 많이 낭비했는데, 그 이유는 입력받는 형태 때문이였다. 3 10 20 30 40 7 5 12 125 15 25 위와 같이 입력값의 개수가 주어지지 않고 개행문자를 입..

티스토리툴바