HJW's IT Blog

문제 설명세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다. 예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추..

문제 설명문제 설명어떤 게임에는 붕대 감기라는 기술이 있습니다.붕대 감기는 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다. t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. 게임 캐릭터에는 최대 체력이 존재해 현재 체력이 최대 체력보다 커지는 것은 불가능합니다.기술을 쓰는 도중 몬스터에게 공격을 당하면 기술이 취소되고, 공격을 당하는 순간에는 체력을 회복할 수 없습니다. 몬스터에게 공격당해 기술이 취소당하거나 기술이 끝나면 그 즉시 붕대 감기를 다시 사용하며, 연속 성공 시간이 0으로 초기화됩니다.몬스터의 공격을 받으면 정해진 피해량만큼 현재 체력이 줄어듭니다. 이때, 현재 체력이 0 이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없습니다.당신은 붕대감..

문제 설명문제 설명한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다.이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다...

문제 설명당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다.처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다.게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 ..

https://school.programmers.co.kr/learn/courses/30/lessons/258709문제 설명A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.다음은 n = 4인 예시입니다.주사위 구성#1[1..

https://school.programmers.co.kr/learn/courses/30/lessons/258711문제 설명도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발..

https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=cpp문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수..

문제 제한사항 fees 배열의 길이는 4 고정 fees[0] = 기본 시간 fees[1] = 기본 요금 fees[2] = 단위 시간 fees[3] = 단위 요금 records 배열은 문자열 배열이다 형식은 [시각 차량번호 IN/OUT] 이다 입차기록이 있지만 출차 기록이 없다면 23:59분에 출차한 것으로 간주한다 주차장에 없는 차량이 출차되거나, 이미 있는 차량이 다시 입차되는 경우는 없다 잘못된 시각은 입력으로 주어지지 않는다. 풀이 문제에서 주차장에 없는 차량이 출차되거나 이미 있는 차량이 다시 입차되는 경우는 없다고 하였다. 즉 같은 차량 번호라면 무조건 -> 입차, 출차, 입차, 출차 순으로 map 을 생성하여 한 차량 번호에 대한 시각을 모두 기록해 놓았다 이때, 시간은 00:00 ~ 23:5..

문제 설명 제한사항 보자마자 dfs를 사용해야 겠다는 생각이 들었다. dfs 를 기저로 깔고, 추가 유의 사항들을 정리해 보았다 라이언 > 어피치 인 경우에만 라이언이 점수를 얻는다 (라이언 = 어피치 or 어피치 > 라이언 인경우 어피치가 점수를 얻는다) 가장 큰 점수차이를 낼 수 있는 방법이 여러가지일 경우 가장 낮은 점수를 더 많이 맞힌 경우 info 배열은 고정크기 11 이다 처음에 dfs 를 구현할 때, 단순히 각 자리에 1씩 추가하며 재귀함수를 도는 방식으로 구현하였다. 그러다 그냥 한번에 어피치가 쏜 화살 개수 + 1 개를 한번에 계산하면 된다는 것을 깨달았다. #include #include #include using namespace std; int ans = 0; vector answe..

문제 정의 이 문제는 피보나치 수열을 재귀적으로 계산하는 함수를 구현하는 문제이다. 재귀 함수만을 이용하여 문제를 풀었을 경우 시간 제한이 있기에 풀 수 없다. 그렇기에 메모이제이션 기법을 통해 문제를 풀었다. 메모이제이션 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하는 다이나믹 프로그래밍 # 테스트 케이스 개수 T = int(input()) # 메모이제이션을 위한 리스트 memo = [[0, 0] for _ in range(41)] memo[0], memo[1] = [1, 0], [0, 1] # 피보나치 수열을 계산하는 함수 def fibonacci(n): # 이미 계산된 값이면 메모이제이션된 값을 반환 if memo[n] != [0, 0]: return memo[n] # 메모이제이션을 위해 이..