본문 바로가기

PS36

백준 1912번 C++ 연속합 연속합https://www.acmicpc.net/problem/1912n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 생각하는 과정이 문제에서 생각해 볼 수 있는 케이스는 연속일 때만을 고려하므로, 두 가지다.i번째를 선택한다는 가정하에1) 연속이 아닐때(i-1번째를 선택하지 않을 때) -> dp[i] 선택(자기 자신만을 가지고 감)2) 연속일 때(i-1번째를 선택할 때) -> dp[i-1]+series[i] 선택(자.. 2019. 5. 30.
백준 1015번 C++ 수열 정렬 수열 정렬https://www.acmicpc.net/problem/1015P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 코드12345678910111213141516171819202122232425#include using namespace std;int main() { i.. 2019. 5. 29.
백준 2133번 C++ 타일 채우기 타일 채우기https://www.acmicpc.net/problem/21333×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 생각하는 과정처음에는 진짜 단순하게 생각했다.일단 N이 홀수이면 홀수x홀수=홀수이기 때문에 2x1, 1x2크기의 타일로 벽을 채우는 것은 불가능하다.따라서 경우의 수는 0그리고 N이 짝수이면 i)N이 2일 때의 세 가지 경우가 있다.ii)N이 4일 때N이 2일 때 각각 왼쪽 오른쪽에 하나씩 붙이는 경우 3*3 + 위 이미지의 경우 상하 반전할 경우 2이런 식으로dp[6]=3*dp[4] + 2*dp[2]dp[2*i]=3*dp[2*(i-1)] + 2*dp[2*(i-2)]라고 했더니 바로괜히 정답률 35퍼가 아니었다... 그래서 스파게티면을 삶으면서 틈틈히.. 2019. 5. 28.
백준 1699번 C++ 제곱수의 합 제곱수의 합https://www.acmicpc.net/problem/1699어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 생각했던 과정7의 제곱수의 합의 최소 개수를 구한다고 해보자.7보.. 2019. 5. 28.
백준 2439번 C++ 어이없는 실수 별 찍기 - 2https://www.acmicpc.net/problem/2439첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. 코드123456789101112131415161718#include using namespace std; int main() { int N, i, j; cin>>N; for(i=1; i0; j--) { cout 2019. 5. 23.
백준 1094번 C++ 막대기 막대기https://www.acmicpc.net/problem/1094지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다.. 2019. 5. 20.
백준 10253번 C++ 헨리 헨리https://www.acmicpc.net/problem/10253 이제 10 살이 된 헨리(Henry)는 수학에 소질이 있다. 수학선생님인 아메스(Ahmes)는 오늘 헨리에게 분수에 대해 가르쳐줬고, 헨리는 분수를 이리저리 계산해보는 것이 너무 재미있었다. 그러던 중에 헨리는 1 보다 작은 분수를 여러 개의 서로 다른 단위분수의 합으로 표현할 수 있다는 것을 알아내었다. 여기서 단위분수란 분자가 1 인 분수를 말한다. 헨리는 여러 개의 분수에 대해 이를 시도해봤고, 시도해본 분수들은 모두 서로 다른 단위분수의 합으로 표현할 수 있었다. 예를 들어, 423은 16+1138와 같이 두 개의 단위 분수의 합으로 나타낼 수 있다. 헨리는 이런 발견을 선생님인 아메스에게 자랑스럽게 이야기했다. 아메스는 이를.. 2019. 5. 20.
백준 1107번 C++ 리모컨 문제 (추가) 현재 상황...반례를 고쳤더니 시간 초과가 떴다그래도 그냥 정리하기 위해 포스팅 나중에 맞으면 다시 고쳐서 올림 (추가) 어제 추가된 틀렸습니다와 시간 초과 ㅋㅋㅋㅋ아마 둘 다 그냥 틀렸습니다겠지 ㅎㅎ저거 원래 있던 코드로 하다가 뻘짓해서 난 결과이다 리모컨은 왜 부수고 난리냐?https://www.acmicpc.net/problem/1107 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.수빈이가 .. 2019. 5. 18.
백준 1157번 C++ 단어 공부 가장 많이 사용된 알파벳 알아내기https://www.acmicpc.net/problem/1157 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 코드1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std; int main() { string word; cin>>word; int listOfWord[26]={0,}; int maxIdx=0, max; for(int i=0; i90) {//아스키코드에서 대문자가 아니면 word[i]=toupper(word[i]); } int .. 2019. 5. 13.

티스토리툴바