본문 바로가기

Problem Solving116

[Problem Solving] BOJ 2022 : 사다리 문제 링크 : https://www.acmicpc.net/problem/2022 다음과 같이 x, y, c가 주어졌을 때, ? 를 구하는 문제이다.좌표평면에 대입하여 피타고라스 법칙을 사용하면 함수 g(x=a, y = b, k=?)가 반환하는 값은 건물 간격이 ?일 때, 높이가 각각 a, b인 사다리의 교점의 높이임을 알 수 있다.이 함수의 값은 k의 값과 반비례한다.  calc = g(x, y, mid)라고 하자,calc의 값이 c보다 충분히 큰 값(c를 포함하는 높이)이라면 일단 answer를 mid로 설정하고, mid를 높여서(low = mid) calc를 낮춰 c와 같도록 만드는 시도를 한다.calc의 값이 c보다 작다면, mid를 낮춰서(high = mid) calc를 높이는 시도를 한다. 이를.. 2025. 3. 2.
[Problem Solving] BOJ 17609 : 회문 문제 링크 : https://www.acmicpc.net/problem/17609 투 포인터를 이용해서 문자열이 회문인지, 유사회문인지, 둘다 아닌지 판별하는 문제이다. left = 0, right = len(s)로 시작해서 left와 right를 각각 오른쪽, 왼쪽으로 이동시킨다. left  s[left] != s[right]가 된다면,s[left + 1 : right + 1](s의 left + 1번째 부터, right 번째를 포함하는 substring)가 회문, 또는 s[left : right](s의 left번째 부터, right - 1번째를 포함하는 substring)가 회문이라면 유사회문이므로 1을 출력하고, 둘 다 그렇지 않다면 2를 출력한다. def is_palindrome(s): lef.. 2025. 3. 1.
[Problem Solving] BOJ 1041 : 주사위 문제 링크 : https://www.acmicpc.net/problem/1041 한 변의 길이가 1인 주사위를 N^3개가 있을 때 이 주사위들로 부피가 N * N * N 정육면체를 만들려고 한다. 보이는 주사위의 눈의 합의 최솟값을 구하는 문제이다. 1) N = 1인 경우 모든 눈의 합을 구한 후, 가장 큰 눈의 합을 뺀 것이 답이 된다. 2) N이 1보다 큰 수일 경우 1. 주사위의 인접한 세 면의 합의 최솟값을 구한다.2. 주사위의 인접한 두 면의 합의 최솟값을 구한다.3. 주사위의 면 중 최솟값을 구한다. 한 변의 길이가 1인 주사위가 N^3개가 있을 때 이 주사위들로 부피가 N * N * N 정육면체를 만들 때, 인접한 세 면이 보이는 주사위는 4개이다.인접한 두 면이 보이는 주사위는 (N - 1.. 2025. 2. 27.
[Problem Solving] BOJ 5427 : 불 문제 링크 : https://www.acmicpc.net/problem/5427 건물에서 탈출해야 하는 데, 불이 탈출구까지 번지기 전에 탈출할 수 있는지, 그렇다면 최소 몇 초만에 탈출할 수 있는지 구하는 문제이다. 1. 사람에 대한 BFS를 수행하여, 사람이 처음 존재하는 격자에서 다른 격자까지 가는데 걸리는 최소 시간을 각 격자마다 구한다. 사람은 불이 최초로 난 곳과 벽을 제외한 모든 곳으로 움직일 수 있다.2. 불에 대한 BFS를 수행하여, 불이 있는 곳으로 부터 각 격자마다 번지게 되는 최소 시간을 계산한다. 불은 벽을 제외한 모든 곳에 번질 수 있다.3. 건물의 탈출구까지 불이 번지기 전에 지훈이가 도달할 수 있는 경우, 도달할 수 있는 시간 중 최소 시간을 구해서 출력한다. 그렇지 못한다면.. 2025. 2. 26.
[Problem Solving] BOJ 16194 : 카드 구매하기 2 문제 링크 : https://www.acmicpc.net/problem/16194 P[i]는 카드 i개가 들어있는 카드 팩의 가격일 때, 카드 N개를 구매하기 위해 지불할 최소 금액을 구하는 문제이다.DP[i]는 카드 i개를 구매하기 위해 지불할 최소 금액이다. dp[i]는 초기값으로 P[i]로 설정한 후,dp[i] = min(dp[i], dp[j] + dp[i - j]) [1 를 갱신해주면 된다. i개는 j + (i - j)개 이기 때문에i개를 구매하기 위해 지불할 최소 금액 = j개를 구매하기 위해 지불할 최소 금액 + (i - j)개를 구매하기 위해 지불할 최소 금액이다. #include #include #include #include #include #include #define endl '\n'.. 2025. 2. 25.
[Problem Solving] BOJ 15684 : 사다리 조작 문제 링크 : https://www.acmicpc.net/problem/15684 주어진 사다리에서 최소 몇 개의 가로 선을 더 추가해야 i에서 출발해서 i에 도착하는 사다리가 되는지 구하는 문제이다. 가로선을 아무리 추가해도 i에서 출발해서 i에 도착하지 못하거나, 4개 이상의 가로 선을 더 그어야 한다면 -1을 출력한다. 가로 선은 연속적일 수 없다. result(): i에서 출발해서 i에 도착하면 true를 반환, 그렇지 않다면 false를 반환.put(a, b): a번째 점선에서 b번째와 b + 1번째 세로선을 연결하는 가로선 생성.remove(a, b): a번째 점선에서 b번째와 b + 1번째 세로선을 연결하는 가로선을 제거.valid(a, b): put을 수행 할 수 있는 곳인지(가로 선이 연.. 2025. 2. 24.

티스토리툴바