본문 바로가기
반응형

acmicpc43

#1325 효율적인 해킹(DFS) 이번 문제는 Silver II 난이도의 문제입니다. 저는 처음에 너무 단순하게 생각해서 한번 틀렸네요. 신뢰관계의 종속성이라는 문제때문인데요. A 가 B를 신뢰하고, B가 C를 신뢰하면, A가 C를 신뢰한다는 사실입니다. 이에 대한 이해도가 틀리면, 해결방법도 당연히 틀리겠죠. 문제의 요지를 살펴보면, N개의 컴퓨터들이 있고, M개의 신뢰관계가 존재할 경우에, 신뢰를 받는 최상위 컴퓨터를 찾는 것입니다. 예를 들면 다음의 그림과 같이 5대의 컴퓨터가 있고, 4개의 신뢰관계가 주어졌다고 해보죠. 화살표 방향으로 신뢰관계가 주어집니다. E는 C를 신뢰하고, C는 A와 B를 신뢰합니다. 직관적으로 보면, 저 위의 그림의 경우에 A 또는 B를 해킹하면, 총 4대의 컴퓨터를 한번에 해킹할 수 있습니다. 전 이 문.. 2020. 1. 24.
#1322 X와 K(Mathematics) 이번 문제는 Gold IV 난이도 문제이지만, 수학적인 원리를 알고 있으면 아주 쉽게 풀 수 있습니다. 주어진 X에 대하여 다음을 만족하는 Y를 구하는데, K번째 Y를 구하는 문제입니다. \[ X + Y = X | Y \] 여기서 | 연산자는 Bitwise OR 로 비트합을 계산합니다. 비트합은 각 비트끼리 논리합(Logical OR)을 합니다. 이를 만족하는 Y 는 X의 비트 중, 1인 부분은 반드시 0이어야 하고, 0인 부분은 1이든 0이든 상관이 없습니다. 만약, X의 비트 중 1인 부분에 같은 위치의 Y의 비트가 1이라고 한다면, 비트합에서는 1이 되지만, 덧셈에서는 0이 됩니다. 어떻게 잘 조합하면 될 것이라고 생각할 수 있지만, 그럴 수 없습니다. X의 비트와 Y의 비트중 같은 위치에 1이 있.. 2020. 1. 23.
#1286 부분 직사각형(구현) 이번 문제는 Gold IV 난이도 문제네요. N개의 줄에 M개의 글자가 각자 써져 있는 문자들을, 3번 복사를 해서 2N개의 줄에 2M개의 글자가 써져 있는 문자들로 만든 다음, 직사각형을 선택해서 부분 문자열들을 만드는 작업을 할 때, 모든 부분 직사각형에 나타나는 문자들의 빈도를 계산하라는 문제입니다. 예를 들어서 ABCD EFGH 라는 2줄에 걸쳐 각각 4글자씩의 문자열이 주어졌다면, 3번 복사를 해서 ABCDABCD EFGHEFGH ABCDABCD EFGHEFGH 를 만들고, 직사각형을 선택해서 필요한 부분문자열을 만듭니다. 예를 들어서 왼쪽위가 (1, 1), 오른쪽 아래가 (3, 2) 직사각형이 있다면, ABCDABCD EFGHEFGH ABCDABCD EFGHEFGH 가 선택되어서, F 글자의 .. 2020. 1. 15.
#1276 교각 놓기(정렬) 이번 문제는 Gold V 등급 난이도라고 되어 있지만, 문제 자체는 아주 쉽습니다. 영어가 제공되는 문제들의 특징들이 문제가 명확하게 설명되어서, 굳이 한글이 번역되지 않은 문제라도 풀만합니다. 2차원상에 다리가 있는데, 이 다리에 교각을 놓으려고 합니다. 다리 밑에 다른 다리가 있는 경우 거기까지만 교각을 세우면 됩니다. 이 때 교각의 총 길이를 계산하면 됩니다. 예를 들어서 다음과 같이 다리가 있다고 해보죠. 왼쪽 그림에서 총 다리가 3개가 있는데, 이 다리에 교각을 내려놓으면, 다른 다리에 얹히는 경우 실제 다리 높이보다 짧은 길이의 교각을 세우게 됩니다. 그렇게 해서 만들어진 교각이 오른쪽 그림입니다. 영어 문제에서는 다리가 서로 겹쳐있지 않다고 했으니까, 예외를 생각하지 않아도 됩니다. 서로 겹.. 2020. 1. 14.
#1256 사전(Combination Digit) 이번 문제는 사실상 조합을 찾아내는 문제입니다. 그런데 조합을 찾기 위한 숫자가 좀 큽니다. 그래보았자, 100이지만요. 난이도는 Gold IV입니다. 정답률은 28.5%이긴 하지만, 크게 어렵지 않았다고 생각했습니다. 문제의 내용을 정리하자면, N개의 a 문자와 M개의 z 문자를 조합하여 사전순으로 배열할 때, K번째 문자열을 출력하는 문제입니다. 예를 들어서 3개의 a와 2개의 z가 있다면 다음과 같이 사전순으로 나열할 수 있습니다. aaazz aazaz aazza azaaz azaza azzaa zaaaz zaaza zazaa zzaaa 이렇게 해서 총 10개의 문자열이 나옵니다. 10개의 문자열이 나온 이유는 5개의 공간 중에 2개의 공간을 선택해서 그곳에 z를 채우고, 나머지 공간에는 a로 채우.. 2020. 1. 13.
백준 #1254 팰린드롬 만들기 팰린드롬(Pallindrome)이라는 것은 앞에서 읽어도, 뒤에서 읽어도 같은 숫자나 단어가 되는 것을 말합니다. 예를 들어서 "a nut for a jar of tuna" 은 공백을 제거하면 팰린드롬이 되는 문귀가 됩니다. 이번 문제는 주어진 단어에 대해서 적절하게 단어 뒤에 문자를 추가하여 팰린드롬이 되는 단어가 되도록 하는 것입니다. 이 때, 가장 짧은 팰린드로의 길이를 찾아내는 문제죠. "abba" 와 같은 경우에는 자체로 팰린드롬이므로 4를 출력하면 됩니다. "banana" 라면 b만 추가하면 "bananab"가 되어 팰린드롬이 되므로 7을 출력합니다. 난이도 Silver II에 정답률 40.6%의 평이한 문제입니다. https://www.acmicpc.net/problem/1254 1254번:.. 2020. 1. 12.
728x90

티스토리툴바