본문 바로가기
반응형

알고리즘63

백준 #1149 RGB 거리 이번 문제는 일렬로 늘어선 집들이 있을 때, 여기에 빨강, 초록, 파랑색으로 집을 색칠하는 것입니다. 색마다 칠하는 비용이 집마다 주어지고, 이웃간에는 색을 달리 칠해야 합니다. 최소의 비용으로 칠을 할 때, 그 비용은 얼마인 가입니다. 문제의 난이도는 Silver I 문제입니다. 정답률도 47.2%로 적당한 수준의 문제입니다. 기초적인 알고리즘 지식만 있으면 풀 수 있는 문제입니다. https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각.. 2020. 1. 5.
백준 #1141 접두사 이번 문제는 접두사문제입니다. 문제의 뜻을 잘 해석 해야 하는데, 접두사 X 집합이라는 뜻을 잘 이해하셔야 합니다. 난이도는 Silver I이며, 정답률은 44.6% 정도입니다. 난이도는 보통이면서 예외가 많지 않은 편입니다. 문제 링크입니다. https://www.acmicpc.net/problem/1141. 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 반면에, {hello, hell}, {giant, gig, g}는 접두사 X 집합이 아니다. 이때, 단어가 N개 주어질 때, 이 단어의 부분 집합 중 접두사X 집합이면서 크.. 2020. 1. 5.
백준 #1138 한 줄로 서기 이번 문제는 문제를 아무리 읽어도 이해하기 힘듭니다. 국어 문제? 난이도는 Silver I인데, 문제를 해석하는데 어려움이 많았습니다. 예제라도 많았다면 유추를 했을텐데, 예제만 가지고 유추하는 것도 힘들었죠. https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 문제를 재해석한다면 다음과 같습니다. 키가 1부터 N까지 사람들이 있습니다. 이들이 어떤 순서로 줄을 섭니다. 키를 그 사람의 번호라고 한다면.. 2020. 1. 4.
백준 #1132 합 이번 문제는 Gold I 난이도입니다. 난이도상으로는 꽤 어려운 문제입니다. 복면산 풀 듯이 풀면 됩니다. 그렇지만, 사실 어려운 문제는 아닙니다. 복잡한 알고리즘이 들어가는 것도 아니고, 구현이 복잡한 것도 아닙니다. https://www.acmicpc.net/problem/1132 1132번: 합 N개의 숫자가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 시작하는 숫자는 없다. 이때, 가능한 숫자의 합 중 최댓값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제는 A~J 로 이루어진 문자열에 숫자를 대입해서 그 숫자들의 합이 최대가 되도록 할 때.. 2020. 1. 4.
백준 #1113 수영장 만들기 블럭으로 쌓아 만든 공간이 있습니다. 블럭 사이사이는 물이 들어가지 않는다고 할 때, 이 블럭위로 물을 충분히 부우면, 얼마만큼 많은 물이 담길까요? 이 문제는 수영장 만들기라는 제목이지만, 내용을 해석해서 간단하게 풀어 말하면 위와 같습니다. 백준 사이트 문제들을 풀다 보면, 프로젝트 오일러 문제와의 차이가, 문제 자체를 누가 명확하게 설명하는가입니다. 백준 사이트는 스토리를 강조하는 느낌들이 많고, 프로젝트 오일러 문제들은 문제 풀기에 집중하는 느낌입니다. 물이 담길려면, 어떤 블럭 A의 높이가 a 라면, 적어도 a+1 이상의 블럭들로 A를 포함한 집단 블럭들을 감싸고 있어야 합니다. 그러면 블럭 A에 물이 담길 수 있습니다. 간단하게 생각하면 쉬운 문제이지만, 이 문제는 Platinum V로 난이도.. 2020. 1. 4.
백준 #1112 진법 변환 일반적으로 우리는 양수 진법 변환에 대해서는 자주 사용했지만, 음수 진법 변환에 대해서는 자주 안 썼죠. 예를 들어서 -10진법이라는 것이 있다면, -10진법 327은 \(327_{-10}=3\cdot(-10)^2+2\cdot(-10)+7=287\)이 될겁니다. 그뿐만 아니라 -10진법으로 63은 \(63_{-10}=6\cdot(-10)+3=-57\)이 되어 실제 음수인데, 표현에는 양수가 되기도 합니다. 예외가 좀 있어서인지 문제 난이도는 Gold II이고, 정답비율은 29.6%입니다. 이 문제가 음의 진법만 다루었다면 편했을텐데, 양의 진법까지 같이 아우르다보니 귀찮은 것이 많아졌네요. 예를 들어서 10진법 -23은 \(-23 = (-2) \cdot 10 + (-3) \) 으로 각 자리수 자체가 음수.. 2020. 1. 3.
728x90

티스토리툴바