본문 바로가기

Algorithm/Greedy17

[백준] 1339. 단어수학 / Java https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 알파벳에 0~9 사이의 수를 대입하여 가장 큰 수를 만드는 문제이다. 핵심은 높은 자릿수에 위치한 알파벳에 큰 수를 맵핑하는 것이다. 예를 들어 아래 두 단어가 주어졌을 때, GCF ACDEB 알파벳별로 따로따로 생각해보면 다음과 같다. GCF = 100*G + 10*C + 1*F ACDEB = 10000*A + 1000*C + 100*D + 10*E + 1*B 그 다음으로는 알파.. 2023. 6. 1.
[백준] 2437. 저울 / 파이썬 (python) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 풀이 문제를 관통하는 키워드는 '누적합'이다. 예를 들어, 아래와 같이 주어졌다고 가정해보자. 4 1 2 4 5 가장 작은 추 하나만 가지고 있는 상태에서 하나씩 추가로 가지게 된다고 생각하면 1만 가지고 있을 때는 측정 가능범위 [0, 1] 2가 추가되면 [0, 1] + [2, 3] = [0, 3] 4가 추가되면 [0, 3] + [4, 7] = [0, 7] 5가 추가되면 [0, 7] + [5, 12].. 2022. 7. 9.
[백준] 1449. 수리공 항승 / 파이썬 (python) 문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다. 입력 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 .. 2022. 6. 26.
[백준] 1543. 문서검색 / 파이썬 (python) 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다. 출.. 2022. 6. 13.

티스토리툴바