본문 바로가기

PS

 (193)
[백준/C++] 14728 벼락치기 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다. 문제에서 주어지는 것을 파악해봤을 때, 배낭 문제와 동일하다는 것을 알 수 있었습니다. 1) 총 시간이 1에서 10000사이의 숫자 2)단원의 개수는 1에서 100 사이의 숫자입니다. 3) 공부시간과 문제의 배점은 1에서부터 1000사이의 숫자입니다. 위의 조건대로 본다면? 이중 for문으로 해결해도 상관이 없고, 자료형도 int로 만들어도 상관이 없습니다. 그래서 내가 갖고있는 시간만큼에서 최대의 점수를 낼 수 있어야 하고, 이 문제의 형식은 배낭문제와 동일합니다. 오늘 배낭문제를 다시 이해를 하게 되었습니다. 일단 제가 이해한 방식을 이렇습니다. 해당 문제는 모든 경우의 수를 따져서 제한된 ..
[백준/C++] 15993 1,2,3 더하기 8 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다. 해당 문제는 더하기 7을 풀고나면 쉽게 풀립니다. 이런 문제는 무엇을 요구하냐면? 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는데, n을 나타낼 때 사용한 수의 개수가 홀수인 방법의 수와 짝수인 방법의 수를 공백으로 구분해 출력하라는 말입니다. 이러 문제는 이전에도 풀었는데, 잘 생각해봐야합니다. 우리는 홀수와 짝수를 구하는 문제인데 어떻게 하면 홀수와 짝수를 잘 구해낼 수 있을까? 이런 문제는 쪼개보는겁니다. 하지만 이 문제를 풀기 전에 그냥 10만이라는 숫자를 보지 못해서 이전에 풀었던거 날먹으로 해결하려고 했으나, 10만에 10만이라 저어어어얼대 시간내로 해결할 수 없어서 새로..
[백준/C++] 12849 본대 산책 사실 엄청 도움되는 글은 아닙니다. 정리가 잘 되어있지도 않고, 거의 직관적으로 문제를 해결해서 제 답이 옳은지 틀린지도 잘 모릅니다.. 아무쪼록 걸러 읽으시길 바라겠습니다.. 저번 글에서 DP를 안해서 하기 싫다고, 내 지식이 탄로나기 싫다고! 이런식으로 적지 않았지만 실제로 이러한 기분이였습니다. 그래도 지식을 채우려면 항상 내가 싫어하는 것을 먼저 해야된다고 생각을 합니다. 그래야 발전도 있고 지루한 일상에서 쾌감도 얻고 뿌듯함도 가져가는 것 아닐까요? 말이 길었네요 실버 1 문제지만 이렇게 좀 의미부여를 해야 확실히 문제를 풀 맛이 나겠죠? 해당 문제는 본대 산책이라는 문제인데, 예전에 문제를 보고나서 이게 뭐야 하고 넘어갔던 적이 있습니다. 그래서 오늘은 풀이를 해보자 생각을 해서 무작정 문제에..
[백준/C++] 2302 극장 좌석 ⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다. DP... Dynamic Programming 사실 DP문제를 좋아하지 않는다. 머리 쓰는거 그렇게 좋아하지 않거든요.. 주어진 조건에 맞춰서 착착착 작성하는게 편하거든요. 타고난 노가다 꾼이 분명한거 같기도 하고.. 어렸을때 현장에서 뛴게 여기서도 발휘되는거 같기도 합니다. 어쨌든 그래도 좋아하는 것만 하고 어떻게 살겠어요. 싫어도 해야지! 차근차근 실버부터 처리를 해봅시다. DP에는 두가지 방식이 존재한다고 하는데 제대로 꼬치꼬치 공부해본적이 없읍니다. 그러므로 아마 이걸 푼게 바텀 업 방식이라고 불리는 것 같은데, 작은것부터 천천히? 일단, 어떻게 풀었냐면? n 사이즈를 보아하니까 41개라..
[시즌2] 6146번 신아를 만나러 0. 문제 https://www.acmicpc.net/problem/6146 6146번: 신아를 만나러 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. www.acmicpc.net 문제 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다. 신아가 ..
[시즌2] 17085번 십자가 2개 놓기 문제 : 중요한 부분 형광펜 칠하기. https://www.acmicpc.net/problem/17085 17085번: 십자가 2개 놓기 첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 문제 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다. 아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈칸은 '.'이다. ...*... ..*.. ...*... .*. ..*.. ...
[백준/c++] 12886 돌 그룹 문제 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다. A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500) 출력 돌을 같은 개수로 만들 수 있..
[백준/c++] 13335 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다. 예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트..

티스토리툴바