뒷북이지만 올려보는 SCON 후기

PS 갤러리
마이너

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

부재중입니다.(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[일기] 뒷북이지만 올려보는 SCON 후기앱에서 작성

행복을좇아

2024.05.13 09:02:22

조회 537 추천 6 댓글 12

대회 중에는 6솔 했었는데 끝나고 다 풀어봤어요. 불꽃놀이의 아름다움은 진짜 모르겠어서 에디토리얼을 봤는데 깔끔한 풀이에 감동의 눈물을 흘렸어요.

7cea8173b08469f03de881ed469f3433943e123504f5c097ab28f800

7cea8173b08760f23dea8fe7459f3433bf460a98d4bc39a76e7de100

A번(과민성 대장 증후군) : 누적합을 만들어서 복통을 겪게 되는 스트레스의 양보다 더 많이 스트레스를 받는 날들을 세어주면 되는 문제였어요.

풀이 : http://boj.kr/3b42c0fa0ab846089a8d7f2b4d76cd62

B번(팀명 정하기 2) : 다음과 같은 기준으로 확인해주면 돼요.

(1) 팀명이 10글자 이하인지

(2) 알파벳 대문자가 소문자보다 같거나 적게 등장하는지

(3) 숫자가 아닌 글자가 하나 이상 포함되어 있는지

for문으로 문자열 확인하는 간단한 문제였어요.

풀이 : http://boj.kr/c11d91d1d4a3422dbbbe34b53738b510

C번(온데간데없을뿐더러) : to_string 함수를 사용해서 이어 붙인 다음에

(1) 자릿수가 다르다면 자릿수가 작은 게 더 작음

(2) 자릿수가 같다면 작은 숫자가 먼저 나온 게 더 작음

의 기준을 비교해주면 풀 수 있는 문제였어요.

풀이 : http://boj.kr/ab8add5a31414db2af5b43b08a7ce7c4

D번(미로 탈출) : 개인적으로 두 번째로 어려웠던 문제였어요. S가 E보다 크다면 S = N + 1 - S, E = N + 1 - E로 바꿔준 다음에 풀었어요. S == 1 && E == N인 경우에만 0번 이동으로 갈 수 있고 나머지의 경우에는 1번 이동하는 모든 경우와 2번 이동하는 모든 경우에 대해서 거리가 더 짧은 경우를 출력하도록 했어요.

풀이 : http://boj.kr/ce83a48b5a954815927e13c91390cf52

E번(수식 고치기) : 동적 계획법 문제였고 저는 dp(i, j, k) := i번째 값이고 연산자가 j, 값이 k일 때 가능한 최솟값으로 놓고 풀었어요.

풀이 : http://boj.kr/01d056de12b3435d96312ee03f8384e4

F번(피보나치 기념품) : 처음에 1...N 이렇게 주어지는 게 아니라 A1...AN 이렇게 주어지는 줄 알고 대회 중에는 포기했던 문제였어요. 그냥 그리디하게 3개씩 짝지어주면 되어요. 대신 마지막에 2, 1이 남았을 때는 이 2개를 짝지어주어야 해요.

풀이 : http://boj.kr/81a400e2aab9475d85d31a9d1e57a8ce

G번(시간표 만들기) : 비트 마스킹을 곁들인 동적 계획법 문제로 이해했어요. dp(i, j, k) := i번째로 일찍 시작하는 수업이고 현재 j 학점을 들었고 각 그룹별로 들은 상태 비트가 k일 때 가능한 경우의 수로 놓고 풀었어요. 제가 최초 솔이었더라고요. 기분이 좋았어요.

풀이 : http://boj.kr/a231d9fe63e04c789c9ca930793f60d1

H번(아이템 2) : 저는 누적합을 곁들인 세그먼트 트리 문제로 이해했어요. dp1(i) := 왼쪽에서부터 i번째 아이템을 마지막으로 골랐을 떄 가능한 최댓값으로 정의하고 풀었어요. 근데 난이도 배정된 걸 보니까 제가 오버킬 했나봐요.

풀이 : http://boj.kr/0ba55554d94b46f58ce95aef709f659c

I번(불꽃놀이의 아름다움) : 이건 에디토리얼 보고 풀어서 할 말이 없어요.

J번(Travelling SCCC President 2) :

(1) 잘못된 접근 : 다익스트라 알고리즘 변형으로 이해했어요. dist(i, j) := 가장 큰 비트가 j번째 비트일 때 i번쨰 정점을 방문하는 최단 거리로 놓고 다익스트라를 돌렸더니 통과되더라고요.

풀이 : http://boj.kr/f7f130dab08447bbb2edc2d22f4132e7

아래 반례가 존재하네요. 제 코드는 15를 뱉는군요.

7cea8173b08a6bff38ea87e0419f343316d522644c3a44c2028970

(2) 새로운 시도 : 유니온 파인드를 이용해서 접근했고 가장 큰 비트부터 보면서 그 비트를 포함하지 않고 이동할 수 있나 60...1까지 총 60번 반복해주면서 조사해줬어요. 포함하지 않아야 하는 비트는 계속 누적해줬어요.

풀이 :

http://boj.kr/e0a0bc943d874275b6d822de50aa83d9

아무튼 다들 좋은 아침이에요~!

- dc official App

고정닉 3

원본 첨부파일 3본문 이미지 다운로드

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2861	설문	어떤 상황이 닥쳐도 지갑 절대 안 열 것 같은 스타는?	운영자	24/05/20	-	-
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	636	12
44058	공지	알고리즘 대회 공부 과정 [21]	*나는최고*	24.04.20	2123	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6753	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21734	30
44925	일반	잘하고 있다는 생각이 안드네요 [4]	ㅇㅇ(106.101)	00:28	147	0
44924	일반	머저리 같이 질문게시판 힌트보고 풀었다 [2]	ㅇㅇ(123.214)	00:27	101	0
44923	일반	레이팅 시스템이 있는 크롬 확장 BOJ Random Defense [9]	mathhater(121.135)	05.23	291	27
44922	일반	골5 dp 6시간 걸렸다 [1]	ㅇㅇ	05.23	160	2
44921	일반	다이야 찍었슴니다 [5]	개드립퍼	05.23	256	9
44920	일반	드디어 플래티넘 성공했습니다 [10]	초6(49.166)	05.23	300	13
44919	팁	우리나라 PS 살리는법 알려준다 [5]	ㅇㅇ(211.234)	05.23	401	16
44918	일반	모니터에 스피커없고 aux도 없으면 [6]	ㅇㅇ(219.250)	05.23	217	19
44917	일반	이런 갤도 있구나 ㅋㅋ 뭔가 반갑네 [6]	ㅇㅇ(211.234)	05.23	262	2
44916	일반	블로그 빼끼고 풀이 배끼고 이거 누구 저격임? [5]	ㅇㅇ(106.101)	05.23	258	0
44915	일반	근데 kmp 같은건 어떻게 생각함? [5]	ㅇㅇ(14.4)	05.23	248	0
44914	일반	피갤컵 A번 문제 스포 [3]	woaldudrl(223.38)	05.23	272	9
44913	일반	이 새끼를 알고나서 내 인생은 바뀌기 시작했다...... [10]	ㅇㅇ(182.225)	05.23	460	3
44912	일반	왜 레이팅이 수시로 변하지 [2]	ㅇㅇ(106.102)	05.23	217	0
44911	질문	이거 어떻게 실행하는지를 모르겠습니다.. [1]	ㅇㅇ(118.221)	05.23	213	0
44910	일반	이 정도 문제도 못 푸는 걸 보니 여긴 진짜 답 없다 [11]	ㅇㅇ(211.36)	05.23	624	29
44909	일기	퍼플떴냐ㄷㄷㄷ [11]	EN_SA	05.23	497	23
44908	질문	혹시 알고리즘 문제 말고 서비스 구현 문제 같은 사이트도 있을까요? [2]	ㅇㅇ(219.241)	05.23	335	0
44907	일반	결국 피갤 고로시 스노우볼로 대회 망하기직전이네… [5]	ㅇㅇ(223.38)	05.23	615	4
44906	일반	피갤컵 call for tasks를 진행합니다! [7]	나는최고	05.22	517	15
44905	일반	뉴비 입문해보려는데 [4]	ㅇㅇ(118.235)	05.22	275	0
44904	일반	2024 IUPC 싸이버거 추첨 [7]	EN_SA	05.22	356	13
44902	일반	UCPC 참가비 관련해서 아이디어 하나 떠오름 [6]	ㅇㅇ(210.0)	05.22	353	0
44901	질문	님들 c언어 뭔 컴파일러씀?(vscode vs vsstduio) [16]	ㅇㅇ	05.22	333	0
44900	일반	코드잼은 왜 없어진거임? [2]	ㅇㅇ(218.158)	05.22	281	0
44899	일반	아이디 새로파서 다이아 3짜리 푸니까 마스터랑 솔브닥이 내꺼 보고갔엇네 [2]	ㅇㅇ(106.101)	05.22	401	2
44898	일반	초기화 잘못된 것도 데추주 대상임? (IUPC) [10]	노는게제일좋아	05.22	341	0
44897	일반	정신나갈것같애 [2]	멍청봇	05.22	219	0
44896	질문	다익스트라 o(n^2)은 잘 사용안하나요? [12]	ㅇㅇ	05.22	426	0
44895	일반	ide 추천점 [3]	ㅇㅇ(106.101)	05.22	121	0
44894	일반	코포 잘 하는 사람이랑 ICPC 문제 잘 푸는 사람이랑 따로 있을 수 있 [9]	ㅇㅇ(106.101)	05.22	407	2
44893	일반	코테말고 프로그래밍 경진대회 같은데서 [7]	ㅇㅇ(117.111)	05.22	312	0
44892	일반	백준 1520 질문 ㄱㄴ? [9]	ㅇㅇ(221.150)	05.22	218	0
44891	일반	코드포스 이 대회는 왜 기한이 17일임? [2]	ㅇㅇ(211.234)	05.22	275	0
44890	일기	배경 뱃지 들어왓냐	EN_SA	05.22	269	11
44889	일반	이 문제 힌트 주실 수 있나요	ㅇㅇ(222.109)	05.22	142	0
44888	일기	실랜디만 확실하게 해도 카카오 컷 넘기는 거 가능하다 [3]	ㅇㅇ(1.230)	05.22	259	2
44887	일반	cubelover 이란 블로그 글보는데 [5]	개드립퍼	05.22	433	0
44884	일반	Codeforces Round #946 (Div. 3) [4]	ㅇㅇ(14.52)	05.22	264	6
44883	일기	골드 1000문제 풀었다! [6]	ㅇㅇ(59.6)	05.21	422	19
44882	일반	왤케 스택문제를 못풀까	ㅇㅇ(180.70)	05.21	133	0
44881	일반	스프라그-그런디 정리 이해하기 [11]	biximo	05.21	708	42
44880	일반	icpc 연습 질문 [4]	ㅇㅇ(175.127)	05.21	201	0
44879	일반	lcs 이 영상 보니 이해 잘 가네 [2]	ㅇㅇ(221.150)	05.21	240	0
44877	일반	Hello 2024까진 잘 열렸지 않음? [3]	ㅇㅇ(122.32)	05.21	349	0
44876	일반	컴공학식 자료구조 배우는데 트리에서 슬슬 막힌다;; [9]	ㅇㅇ(220.73)	05.21	357	1
44875	일반	ucpc 좀 씁쓸하네 [7]	ㅇㅇ(118.235)	05.21	509	2
44874	일반	CP 실력올리기 질문 [5]	물감비	05.21	302	0
44873	일반	딥3 등수가 왤케 올라갔지 [1]	ㅇㅇ(106.101)	05.21	133	0
44872	일반	코포 딥3 채점 왜이리 오래걸리지	ㅇㅇ(203.255)	05.21	67	0