본문 바로가기
반응형

BOJ50

#1476 날짜 계산 이번 문제는 난이도는 Silver V로 쉬운 편입니다. 수학적 지식을 가지고 있다면 손쉽게 풀 수 있습니다. E, S, M 이란 단위가 1부터 시작해서 각각 15, 28, 19 의 범위를 가지는데, 모두 같이 증가하기 시작해서 16이 되면 E의 값은 1이 됩니다. 즉 다음과 같이 움직이게 되죠. 1 1 1 -> 2 2 2 -> 3 3 3 -> ... -> 15 15 15 -> 1 16 16 -> 2 17 17 -> ... -> 4 19 19 -> 5 20 1 -> ... 우리가 얻고자 하는 숫자가 x년도라면, E, S, M은 다음과 같이 표현할 수 있습니다. \[ ( (x-1)~ mod~ 15 + 1, (x-1)~ mod~ 28 + 1, (x-1)~ mod~ 19 + 1 ) \] 15, 28, 19 는 .. 2022. 8. 19.
#1475 방 번호 이번 문제는 Silver V 수준이라고 되어 있지만, 그것보다는 조금 더 쉬운 듯 합니다. 방번호를 하나 주고, 그 방번호를 0부터 9까지의 숫자를 이용해서 표현하기 위해서는 몇개의 숫자셋이 필요한가입니다. 예를 들어서 3457 이란 숫자이면 하나의 숫자셋으로 표현이 가능하죠. 숫자들이 몇번 나타났는지 세면 가장 좋겠죠. 단 6과 9는 혼용해서 쓸 수 있으므로, 6과 9의 숫자 개수는 더한 다음 2로 나누면 됩니다. 홀수인 경우에는 1 많게 하기 위해서, \[ \lfloor (n(6) + n(9) + 1)/2 \rfloor \] 형태로 사용토록 합니다. 다음은 제가 작성한 코드입니다. 코드는 참조용으로만 봐주세요. //------------------------------------------------.. 2022. 8. 18.
#1464 뒤집기 3 이 문제는 Gold V 문제입니다. 문자열이 주여졌을 때, 처음 1글자를 뒤집을 수도 있고, 아닐 수도 있습니다. 다음에는 처음 2글자를 뒤집을 수도 있고 아닐 수도 있죠. 이렇게 해서 총 글자수대로 뒤집을 수도 있고 아닐 수도 있습니다. 예를 들어서 "CDEFA" 란 문자열이 주어진다면, 1글자에서는 뒤집지 않는다를 선택하면 "CDEFA" 그대로 나오겠죠. 2글자에서 뒤집기를 한다면, "CD"가 뒤집혀서 "DCEFA"가 됩니다. 3글자에서 뒤집지 않는다를 선택하면 그대로 유지되고 4글자에서 뒤집기를 한다면, "DCEF"가 뒤집혀서 "FECDA"가 됩니다. 5글자에서 뒤집기를 한다면, "ADCEF"가 나옵니다. 이렇게 뒤집기를 선택했을 때 나올 수 있는 단어중 가장 앞에 나오는 단어를 얻도록 만드는 것이.. 2022. 8. 18.
#1457 정확해 정확해라는 문제는 약수들의 합을 구하는 문제입니다. 난이도는 Gold I 문제이긴 하지만, 이게 수학적인 이해를 하지 못 하면 조금 어렵습니다. 그래서인지 정답자가 제가 푼 시점에서는 40명에 그칩니다. 약수의 개수를 구하는 문제는 꽤 어렵습니다. \[ \sigma_0(n) = n( \lbrace x | n~ mod~ x = 0 \rbrace ) \] 으로 약수를 구하는 식을 사용한다면, \(\sqrt{n}\)에 해당하는 만큼 약수가 되는 개수를 구하던지, 소인수 분해를 해주어야 합니다. 그런데 만약 1 부터 n까지의 약수들의 개수의 합을 구하라는 문제라면 어떨까요? \[ S(n) = \sum_{k=1}^{n} \sigma_0(k) \] 하나의 수의 약수의 개수를 구하는 것도 어려운데, 일정 숫자 범위의.. 2022. 8. 16.
#1456 거의 소수 이번 문제는 소수를 구하는 문제입니다. 난이도는 Silver I 정도로 평가됩니다. 소수를 구하는 방법은 여러가지가 있는데, 일단은 2부터 n까지 숫자중 소수를 구하는 것이라면 \(O(n \sqrt {n} )\) 정도의 알고리즘으로 구할 수 있습니다. 에라토스테네스의 체를 이용하면, 메모리 공간이 좀 들겠지만, 가장 준수한 효율로 소수를 구할 수 있습니다. 거의 소수는 소수 \(p\)에 대해서 \(p^N\) 형태로 표현되는 수를 말합니다. 소수 자체는 거의 소수가 아니므로 실제로 주어진 범위안에서 구할 소수는 \( \sqrt {n} \) 범위입니다. 주어진 범위가 a ~ b 까지이므로 2 ~ b 까지의 거의 소수 개수를 구한 후 2 ~ a-1 까지의 거의 소수 개수를 빼주면 됩니다. 숫자의 범위가 \(1.. 2022. 8. 11.
#1445 일요일 아침의 데이트 일요일 아침의 데이트는 다익스트라 알고리즘을 이용하는 문제로 Gold II 문제로 잡혀 있습니다. 아침에 산책을 하면서 야외에서 커피를 같이 마시면 즐겁겠죠? 다익스트라 알고리즘을 알고 있는 분들은 어렵지 않게 풀 수 있습니다. 일단 맵을 읽으면, 이 맵을 적절하게 변환을 해주었습니다. 예제와 같이 입력이 주어진다면, 6 6 ...... g..F.. ...... ..g... ...... ...S.g 저는 이 입력을 다음과 같은 형태로 변환을 했습니다. 쓰레기가 있는 주변을 1로 만들고, 쓰레기는 10,000의 값으로 채웠습니다. S, F는 세지 않는다고 했으니, 추후에 그 부분은 다시 0의 값으로 만들고요. 1 0 0 0 0 0 10K 1 0 0 0 0 1 0 1 0 0 0 0 1 10K 1 0 0 0 .. 2022. 8. 9.
728x90

티스토리툴바