# acmicpc
1789번: 수들의 합 python
programmers 코테 고득점 kit - (분야) - (문제 이름)서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?ex) s : 200 N의 최대값: 1,2,3,4,5...,17,18,29(19개)첫째 줄에 자연수 S(1
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)첫째 줄에 구한 0의 개수를 출력한다.처음 문제를 보고 든 생각은 dp 였다. n의 수가 크기 때문에 팩토리얼 값을 구하고
1181번: 단어 정렬 python
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터길이가 같으면 사전 순으로첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어
4673번: 셀프 넘버 python
셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d
다리 놓기 1010번 python
programmers 코테 고득점 kit - (분야) - (문제 이름)강 서쪽에서 동쪽으로 이어진 다리가 서로 겹쳐지지않게 놓을 수 있는 경우의 수를 구하여라입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과
개똥벌레(3020) / python
acmicpc 코테 준비 문제 - 구현 - 개똥벌레 3020번 - python제한 사항 첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기
럭키 스트레이트 / python
acmicpc 코테 - 구현 - 럭키 스트레이트문제 설명어떤 게임의 아웃복서 캐릭터에게는 럭키 스트레이트라는 기술이 존재한다. 이 기술은 매우 강력한 대신에 항상 사용할 수는 없으며, 현재 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다.특정 조건이란 현
뒤집기(1439) / python
백준 - 탐욕법(greedy) - 뒤집기(1439번) 문제 설명다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집
불 끄기
Problme link: https://www.acmicpc.net/problem/14939행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자.i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정
가장 긴 증가하는 부분 수열 5
Problme link: https://www.acmicpc.net/problem/14003별로 특별할 것 없이 lower_bound를 사용해서 풀어주면 LIS의 길이까지는 무리 없이 구해줄 수 있다.여기서 실제 LIS를 재구성해내는데 조금 어려움을 겪었는데,
1로 만들기 2
Problme link: https://www.acmicpc.net/problem/12852포인트 냠냠을 위한 BFS 문제이다.숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.
본대 산책 2
Problme link: https://www.acmicpc.net/problem/12850Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자.이때, M\[i]\[j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자.이렇게하면,
가장 긴 증가하는 부분 수열 2
Problme link: https://www.acmicpc.net/problem/12015사람마다 푸는 방법은 여러가지가 있을텐데, 나는 그중에 가장 무지성으로 풀 수 있는(물론 복잡도는 다른 알고리즘에 뒤지지 않는다) lower_bound 풀이를 사용했다.
행렬 곱셈 순서
Problme link: https://www.acmicpc.net/problem/11049그닥 어려울 것 없는 DP 문제로 쉽게 쉽게 풀어줄 수 있다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e]: Matrix\[s]부터 Matrix\[e]까지
팰린드롬?
Problme link: https://www.acmicpc.net/problem/10942문제 설명이 조금 부족한데, 숫자 하나를 문자 하나로 취급해야 한다.여튼 노말하게 DP를 써주면 풀리는 문제이다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e
공항
Problem link: https://www.acmicpc.net/problem/10775이진 트리(i.e. std::set)을 활용해서 풀어주었다.쉽게 풀고나서 혹시나 하는 마음에 문제 분류를 보니 Disjoint Set을 활용해서도 풀어줄 수 있는 모양이