수학

    [BOJ] 9519 - 졸려
    BOJ

    [BOJ] 9519 - 졸려

    문제 출처 [BOJ] 9519 - 졸려 풀이 눈을 깜빡인 횟수를 모두 돌아주어 문자열의 상태를 알아낸다면 시간초과가 날 것입니다. 그래서 다른 방법을 찾아야 합니다. 문제의 문자열이 바뀌는 규칙대로 쭉 써보다보면 규칙을 찾을 수 있습니다. 위의 사진과 같이 원래의 문자열로 돌아오는 주기가 있고 위의 예제는 5번 눈을 깜빡이면 다시 원래의 상태로 돌아오게 됩니다. 그렇다면 X를 주기만큼 나눈 나머지 값만큼 문자열을 바꿔준다면 정답을 구할 수 있습니다. 이 때 나머지 값만큼 문자열을 바꿔줄때는 정해진 규칙의 반대로 문자열을 바꿔주어야 눈을 깜빡이기 전 원래의 문자열을 찾을 수 있습니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm development by ..

    BOJ

    [BOJ] 11812 - K진 트리

    문제 출처 [BOJ] 11812 - K진 트리 풀이 자식을 최대 K개 가질 수 있는 K진 트리에 있는 노드들 중 주어진 두개의 노드 사이의 거리를 구하는 문제였습니다. 두개의 노드가 주어지면 해당 노드의 부모노드를 찾고, 부모노드의 부모노드를 찾는 과정을 쭉 반복하면서 루트노드인 1을 만날때 까지 저장해주어 저장해준 값을 비교하면서 부모노드가 달라지는 경우를 판단해 거리를 구해주었습니다. 부모노드를 찾는 수식은 다음과 같습니다. 부모노드 = (현재 노드 + K -2) / K 코드 small-j/Algorithm Contribute to small-j/Algorithm development by creating an account on GitHub. github.com

    BOJ

    [BOJ] 16936 - 나3곱2

    문제 출처 백준 16936 - 나3곱2 풀이 나3 : 3으로 나누어 3으로 나누어떨어지는 수 곱2 : 2를 곱함 이렇게 나3곱2를 한 수들을 나열하여 수열을 만들 수 있는데 그 수열을 섞어서 입력이 주어집니다. 그리고 그 수열을 찾는 것이 문제입니다. 위의 방법처럼 원래 수에 곱2한 값을 저장해주고 나3을 해주어 나누어떨어진다면 저장해주었습니다. 원래 수들을 차례대로 돌면서 각각을 시작수로 놓고 시작수에서 나3 하거나 곱2한 값이 원래 수에 존재한다면 그 원래 수에서 또다시 나3곱2한 값을 보고 다음 수를 찾아주는 방법으로 수열을 찾아주었습니다. 만약 나3곱2한 값이 원래 수에 존재하지 않는다면 멈춰주었고 한번 수열을 찾으면 멈추었습니다. 코드 small-j/BOJ_Algorithm Contribute ..

    BOJ

    [BOJ] 1612 - 가지고 노는 1

    문제 출처 백준 1612 - 가지고 노는 1 풀이 11, 111, 1111, 11111 .... 처음에는 큰 수 계산이 가능한 파이썬으로 위처럼 한자리씩 늘려가며 수를 만들어 계산해주려 했지만 시간초과가 납니다. 파이썬도 수가 커질수록 연산을 수행하는데 오래 걸리기 때문입니다. (11 % N 의 나머지) * 10 + 1 이 처럼 작은 단위로 나누어 계속 늘려주면서 계산하여 수가 길어지는 문제점을 해결했습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com

    BOJ

    [BOJ] 1484 - 다이어트

    문제 출처 백준 1484 - 다이어트 풀이 엔토피아가가 선물해준 저울로 젠 G 킬로그램이 주어지면 성원이의 현재 몸무게로 가능한 것을 모두 구하는 문제였습니다. G 킬로그램 = {성원이의 현재 몸무게}2 - {성원이가 기억하고 있던 몸무게}2 G는 100,000 보다 작거나 같기 때문에 무작정 큰 수까지 돌려서 제곱 - 제곱의 조합을 찾기에는 시간초과가 날 것입니다. 그래서 어떤 상한선이 있을 것이라 생각했고 수가 커질수록 제곱 - 제곱의 결과가 커진다는 것을 알아내어 제곱 - 제곱의 결과가 G보다 커지는 경우 더이상 몸무게를 찾지 않도록 해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating ..

    BOJ

    [BOJ] 18291 - 비요뜨의 징검다리 건너기

    문제 출처 백준 18291 - 비요뜨의 징검다리 건너기 풀이 비요뜨가 1번 징검다리에서 마지막 징검다리까지 도달하여 강을 건너는데 경우의 수를 구하는 문제였습니다. 경우의 수가 2N-2의 규칙을 가지고 있고 징검다리의 개수가 최대 109까지 이기 때문에 그대로 계산한다면 109 + 7로 나눈다고 해도 너무 큰 수가 되버려 long long 범위를 넘어가버립니다. 따라서 (28) -> ((22)2)2 이런 식으로 재귀함수를 돌려 계산해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com

    BOJ

    [BOJ] 2502 - 떡 먹는 호랑이

    문제출처 백준 2502 - 떡 먹는 호랑이 풀이 주어진 날이 x라면 x-1날은 주어진 날 전날을 말합니다. x(떡의 갯수) - x-1(떡의 갯수) = x-2(떡의 갯수) 즉, 주어진 D째 날에서 전날의 떡의 갯수를 빼주는 방식으로 전전날의 떡의 갯수를 구했습니다. x-1(떡의 갯수)를 구하기 위해서 현재 날짜의 떡의 갯수보다 작은 경우를 모두 가정하여 빼주었습니다. 예를 들어 7번째 날의 떡의 갯수가 7개라면 6~1까지 떡의 갯수를 빼주었습니다. 주어진 D째 날의 떡의 갯수에서 전날의 떡을 빼주는 과정을 D만큼 반복하여 첫째 날까지 나누어 줄 수 있는지 직접 돌려 보았다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development b..

티스토리툴바